알고리즘 - 정렬

정렬 (Sorting) 이란?

 

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

 

[12, 6, 4, 17, 11, 15, 1, 30]   →   [1, 4, 6, 11, 12, 15, 17, 30]  // 오름차순

 

[12, 6, 4, 17, 11, 15, 1, 30]   →   [30, 17, 15, 12, 11, 6, 4, 1]  // 내림차순

 

['cat', 'apple', 'egg', 'banana', 'dog']   →   ['apple', 'banana', 'cat', 'dog', 'egg']  // 알파벳순

 

 

📍 선택 정렬 (Selection Sort)

 

가장 먼저 생각이 날 수 있는 자연스러운 정렬 알고리즘

 

가장작은 값을 찾아서 0번 인덱스에 놓고

 

두번째로 작은 값을 찾아서 1번 인덱스에 놓고

 

세번재로 작은 값을 찾아서 2번 인덱스에 놓고

 

이러한 방식으로 계속 진행하여 정렬하는 방식이다.

 

 

📍 삽입 정렬 (Insertion Sort)

 

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

삽입 정렬은 두 번째 요소부터 시작하여 그 앞의 요소들과 비교하여 삽입할 위치를 지정한 요소를 뒤로 옮기고 지정한 자리에 요소를 삽입하여 정렬하는 알고리즘이다.

 

두 번째 요소는 첫 번째 요소. 세 번째 요소는 두 번째와 첫 번째, 네 번째 요소는 세 번째, 두 번째, 첫 번째 요소와 비교한 후 요소가 삽입될 위치를 찾는다.

 

요소가 삽입될 위치를 찾았다면 그 위치에 요소를 삽입하기 위해 요소를 한 칸식 뒤로 이동시킨다.

 

처음 Key 값은 두 번째 요소부터 시작한다.

 

 

 

선택정렬

각 위치에 어떤 값이 들어갈지 찾는다.

삽입 정렬

각 값이 어떤 위치로 들어갈지 찾는다.