Python: 선택 정렬, 삽입 정렬, 버블정렬, 병합정렬

[ 선택 정렬 ]

index 0~8번 까지 각각 선택해서 알고리즘이 진행된다.

선택한 요소의 이후요소들 중 선택한 요소보다 작은 값이면서 최소값을 구한 뒤 swap한다.

 

 

 

[ 삽입 정렬 ]

리스트 list = [4,2,7,1,6]이 존재한다고 하자.

list[0]인 4는 그대로 두고 1번 index부터 마지막 요소까지 알고리즘에 넣어준다.

첫번 째 요소는 처음 알고리즘 실행 시 1번 인덱스값과 비교하기 위해서 건들지 않는다.

1. 요소를 선택

2. 해당 요소와 이전 인덱스 값을 비교한다. 해당 값보다 작다면 둘의 위치를 바꾼다.

3. 이 작업을 0번째 인덱스와 비교할 때 까지 계속한다.

 

 

 

[ 버블 정렬 ]

앞에 수가 뒤에 수보다 큰 경우 서로 위치를 변경한다. 

앞에 수가 뒤에 수 보다 작은 경우 아무런 변화가 없고 뒤에 수는 다음 뒤에 수와 비교된다.

 

 

 

[ 병합 정렬 ]

[ 4, 2, 3, 1 ] 배열이 있다고 하자.

반으로 나눠서 left = [ 4, 2 ] , right = [ 3 , 1 ]

left는 다시 [4] ,[2] 로 나뉘고 right 는 다시 [3], [1] 로 나뉜다.

[4]는 left의 left이고 [2]는 left의 right    => merge( [4], [2] ) => result = [ 2, 4 ]

[3]은 right의 left이고 [1]은 right의 left    => merge( [3], [1] ) => result = [ 1, 3 ]

마지막으로 merge( [2,4] , [1,3] )    => 배열에 1,2,3이 채워진 뒤 extend함수를 통해 4가 채워진다.