정렬 알고리즘 - ( 버블 정렬, 삽입 정렬, 선택 정렬 )

********************************************************************************************************

INDEX

** 버블정렬 이란?

** 삽입정렬 이란? 

** 선택정렬 이란?  

********************************************************************************************************

** 모듈화와 인자 ( T,F) 에 따라서 옵션을 주는 연습을 하자 

** 버블정렬 이란? 

> 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘 

[5,1,2,3,4] 시작, 5와 1 비교 후, 5>1 이니 스위치 [1,5,2,3,4]

-----------

[1,5,2,3,4] 2와 5 비교 후, 5>2 이니 스위치 [1,2,5,3,4]

[1,2,5,3,4] 3와 5 비교 후, 5>3 이니 스위치 [1,2,3,5,4]

[1,2,3,5,4] 4와 5 비교 후, 5>4 이니 스위치 [1,2,3,4,5]

-----------

[1,2,3,4,5]

 

 

** 정렬 사용시 깊은 복사와 얕은 복사 

* bubble_sort 모듈 생성 시,

import copy

 

if deepCopy==True:

    new_copy = copy.copy(original)

else:

    new_copy = original 

을 미리 설정한다. 이후 sort_module.function_bubble_sort(data,deepCopy=T/F)에서 인자를 바꿔서 깊/얕 복 여부 전환 가능

 

** 삽입정렬 이란? 

 

> 정렬되어 있는 자료 배열과 비교해서 정렬의 위치를 삽입하는것. 

> 비교 대상인 수를 입력한 후, 비교 대상 수의 원래 위치에 숫자를 삽입 

> 오름차순으로 시행하였으나, 부호를 바꿔주면 내림차순으로 변경 가능 

 

[1,2,5,3,4] 시작, 5와 정렬되어 있는 [1,2]와 비교, 순서 유지

-----------

[1,2,5,3,4] 3과 정렬상태인 [1,2,5] 비교 , 3<5 이니 스위치 [1,2,3,5,4]

[1,2,3,5,4] 4와 정렬상태인 [1,2,3,5] 비교 , 4<5 이니 스위치 [1,2,3,4,5]

-----------

[1,2,3,4,5]

 

단편적으로,

[6,11,3,2,1] 일 경우, 정렬되어 있는 [6,11] 과 3부터 비교 시작 

[6,11,11,2,1] -> [6,3,11,2,1] -> [3,3,11,2,1] -> [3,6,11,2,1]

[3,6,11,2,1] 정렬되어 있는 [3,6,11]과 2 비교 

[3,6,11,11,1] -> [3,6,2,11,1] -> [3,2,2,11,1] -> [3,2,6,11,1] -> [3,3,6,11,1] -> [2,3,6,11,1]

 

* for 문에서는 전체 숫자 range(1,len(nums)) 하여 0이 아닌 두번째 인덱스1 부터 마지막 자리 인덱스 5까지 시행한다 

* i1은 비교를 할 숫자

* i2는 i1 - 1 으로, 비교 대상인 하나 아래의 인덱스를 말한다 

* c_num = nums[i1]은,  비교를 할 숫자 ( 정렬 대상 ). 

while 조건문을 실행한다. 

* 비교 대상이 > 비교 숫자보다 크고(앤드) 비교 대상의 인덱스 넘버는 0 이상일 경우에 

비교 대상의 인덱스 + 1 ( 다음위치) (3의 자리)에 비교 대상 하나 아래의 인덱스 11을 저장한다. 

그리고 인덱스를 하나씩 낮춘다 i2 -= 1  

while문이 돌아가고 있으므로,  [n,n, 여러 수들 .. ] 의 형태로 정렬이 계속될 것이다.

while문 종료는  i2 값이 -1이된 시행부터인데, i2 값이 while문 시행 기준으로 0인 경우이다. 그럼 i2가 -1이 되면서 조건문이 종료된다.

마지막으로는 nums[i2+1] 이 nums[0]이 되면서, while문 이전에 보존하고 있던 비교를 할 숫자 c_num이 0번째 인덱스에 쓰여진다. 

 

** 선택정렬 이란?  

> 주어진 리스트에서 최소값을 찾아서 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정리하는 방법이다  ( 오름차순 정렬 기준 ) 

> 중첩 for문으로 해결 

 

[1,2,5,3,4] 시작, 3은 1,2 이후 최소값이니 이동

-----------

[1,2,3,5,4] 4는 1,2,3 이후 최소값이니 이동 

-----------

[1,2,3,4,5]

 

* 크게 두가지 과정이다

* i번 인덱스와 뒤부터 최솟값을 찾고, 그 인덱스를 찾는다

* i번째 값에 최솟값을 넣는다, 그 값을 맨 앞의 값과 교체한다

 

** 모듈화 연습