리스트의 원소들을 특정 순서로 정리하는 것
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
거의 정렬된 리스트를 정렬할 땐 삽입 정렬이 가장 빠름
무작위의 리스트를 정렬할 때는 힙 정렬이 가장 빠름
선택 정렬과 합병 정렬은 일정한 시간 소요
'알고리즘' 카테고리의 다른 글
[알고리즘] 재귀함수 (0) | 2021.05.19 |
---|---|
[알고리즘] 탐색 (0) | 2021.05.04 |