[알고리즘] 정렬

리스트의 원소들을 특정 순서로 정리하는 것

 

list = [3, 2, 4, 5, 1, 6]

 

선택 정렬

각 위치에 어떤 값이 들어갈지 찾음

가장 작은 값을 찾아서 0, 그 다음 작은 값 1,,,, 이런 순으로 작은 값 먼저 인덱스 지정

list에서 가장 작은 값을 찾는다. list에서는 5번 인덱스가 가장 작다.

첫번째 인덱스 0과 자리를 바꾸고 후 다음 비교에선 0번 인덱스는 제외해줌..

 

가장 작은 값을 찾고 비교한 인덱스 중 첫 인덱스랑 값 바꿈

그러면 첫번째인덱스에 가장 작은 값이 들어가있음

가장 작은 값이 첫번째 인덱스에 있기 때문에 다음 비교에선 필요없으니 제외하고

다시 비교... 반복

 

 

삽입 정렬

각 값이 어떤 위치에 들어갈지 찾음

새로운 값이 들어왔을때 기존에 정렬된 값중 어느 위치에 넣을지 정하는 것

list에서 첫번째인덱스를 기준으로한다. list1 = [3]

다음 2가 들어갈 자리를 찾는다. 3과 비교 후 3보다 작으니 왼쪽에 위치하게 된다. list1 = [2, 3]

다음 4는 3보다 크니 오른쪽에 위치하게 된다. list1 = [2, 3, 4]

5도 마찬가지로 4보다 커서 list1 = [2, 3, 4, 5]

다음 1은 5와 비교 후 5보다 작아서 왼쪽에 있는 4와 비교한다. 4보다 작으니까 3과비교,, 2와 비교 후 list1 = [1, 2, 3, 4, 5] 가 된다.

 

 

 

 

 

 

www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

거의 정렬된 리스트를 정렬할 땐 삽입 정렬이 가장 빠름

무작위의 리스트를 정렬할 때는 힙 정렬이 가장 빠름

선택 정렬과 합병 정렬은 일정한 시간 소요