정렬 알고리즘 - 1. 선택 정렬(index) / 2. 삽입 정렬(value)

이글은 코드잇의 알고리즘 강의와 오픈소스들을 참고하여 정리한 글입니다^^

정렬(Sorting) : 리스트의 원서들을 특정 순서로 정리하는 것

• 오름차순, 내림차순, 알파벳순
• python에는 이미 sorted( list ) 내장함수나 리스트의 list..sort() method도 있다.

그냥 sorted()나 .sort()를 쓰면 될 것 같으나 정렬을 왜 배워야 할까?
그 이유는 정렬 자체가 알고리즘의 기초 & 모든 개발자가 알아야할 가장 기본적인 알고리즘이기 때문이다.

1. 선택 정렬(Selection Sort) : 각 인덱스에 들어갈 값들을 찾아서 정렬하는 알고리즘으로서,
   가장 작은 값 -> 0번 인덱스
   2번째 작은 값 -> 1번 인덱스
   3번째 작은 값 -> 2번 인덱스 ... 방식으로 정렬한다.
   예를들어,
   

   • 0번 인덱스에 넣어줄 가장 작은 값을 찾기위해, 0~5번 인덱스의 값들을 확인한 뒤 넣어준다.

   • 0번 인덱스의 값을 볼때는, 4가 가장 최소값이다.

   • 1번 인덱스의 값을 볼때는, 2가 가장 최소값이다.

   • 3번 인덱스의 값을 볼때는, 1가 가장 최소값이다.

   • 5번 인덱스까지 1회전 다봤으면,
     0번 인덱스의 값 <-> 3번 인덱스의 값(최소값)을 교체한다.

   • 이제 1번 인덱스에 들어갈 값을 찾기위해서, 1 ~ 5번 인덱스까지 값을 보고 가장 작은 값과 교체해준다.

   • 마찬가지로 2번 인덱스 -> 2~5번 인덱스의 값 탐색 후 가장 최소값 넣어주기 -> 반복한다.

2. 삽입 정렬(Insertion Sort) : 각 값이 어떤 인덱스에 들어가야할지 찾는 알고리즘으로서,
   예를 들어, 카드 게임을 한다고 할 때, 이미 정렬된 카드를 가지고 있는 상태에서 딜러가 새로운 카드를 줬을 때, 새로운 카드를 올바른 위치에 삽입(끼워넣는)한다.

my) 0과1 정렬/ 0,1,2 정렬/ 0,1,2,3 정렬 하는데, 마지막값을 기준으로 왼쪽으로 차례차례 비교해나간다.


아래와 같은 리스트가 있다고 가정하자.

- 먼저, 0번과 1번 인덱스의 값만 보고, 정렬한다.

- 다음으로, 0,1,2번 인덱스의 값을 보고, 정렬한다.

- 다음은, 0,1,2,3번 인덱스의 값을 보고 정렬한다. 이 때, 3값<->2값, 2<->1값, 1값<->0값순으로 한번씩 비교하는 것 같다.





- 마지막 5번인덱스의 값 3은,
(1) 9와 비교해서 왼쪽,
(2) 7과 비교해서 왼쪽,
(3) 4와 비교해서 왼쪽, 총 3번을 한칸씩 움직인다.

참고)

• 이미 거의 정렬된 리스트를 정렬할 때는 삽입 정렬(Insertion Sort)이 가장 빠른 반면,
• 아예 정반대로 정렬된 리스트의 경우에는 삽입 정렬이 매우 오래 걸린다는 것도 볼 수 있죠.
• 선택 정렬(Selection Sort)과 합병 정렬(Merge Sort)은 상황에 영향을 받지 않고 일정한 시간이 소요된다는 점도 주목해 볼 만합니다.
• 무작위 순서의 리스트를 정렬할 때는 힙 정렬(Heapsort)이 가장 먼저 끝나네요.

구현시 참고 블로그 : http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html