0. 정렬

정렬의 방법은 여러가지가 있습니다.
그 중에서도 오늘 저희는 버블, 선택, 삽입 세가지 정렬에 대해서 알아보려 합니다.

👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.

1. 버블정렬

버블 정렬이란, 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식을 이야기합니다.

쉽게 설명하자면, 버블이 뭡니까, 거품이죠.

거품은 항상 물 위로 뜨려는 성질이 있습니다.

이처럼 거품이 위로 떠오르듯이, 특정 값이 인접 요소와 비교되어 가라 앉거나 떠오르는 방법으로 정렬하는 것입니다.

버블정렬 수행과정

1. 비교 연산이 필여한 루프의 범위를 설정합니다.
2. 인접한 데이터 값을 비교합니다.
3. swap 조건에 부합하면 swap합니다.
4. 루프 범위가 끝날 때 까지 2~3을 반복합니다.
5. 정렬 영역을 설정합니다. 다음 루프를 실행할 때는 이 영역을 제외합니다.
6. 비교 대상이 없을 때 까지 1~5를 반복합니다.

보시다시피, 버블 정렬 수행 과정은 상당히 반복적입니다.

간단히 구현이 가능하지만, 시간복잡도는 O(n**2)으로 속도가 느린 편입니다.

2. 선택정렬

선택정렬이란, 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법입니다.

선택정렬은 최소값 또는 최대값을 찾고 정렬되지 않은 부분의 가장 앞에 있는 데이터와 swap하는 방식으로 정렬하는 방법입니다.

구현방법이 복잡하고 시간 복잡도 또한 O(n**2)로 효율적이지 못합니다.

선택정렬 수행과정

1. 남은 정렬 부분에서 최소값 또는 최대값을 찾습니다.
2. 남은 정렬부분에서 가장 앞에 있는 데이터와 1에서 선택한 데이터를 swap합니다.
3. 남은 정렬 부분의 범위를 축소하고, index++ 연산을 수행합니다.
4. 전체 데이터 크기만큼 index가 커질때 까지, 즉 남는 정렬 부분이 없을 때까지 반복합니다.

3. 삽입정렬

삽입정렬이란, 이미 정렬되어있는 데이터에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식입니다.

이게 대체 무슨 소리야 하실 수 있겠지만,

쉽게 이야기해보자면...

여러분들 트럼프카드로 게임한다고 할때 손에 자기 패 나름 순서대로 정렬하지 않습니까,
아니면 루미큐브 블럭 정리할때 나름대로 정리하지 않습니까,

그냥 자리 찾아서 꽂아넣고 말지
버블정렬이나 선택정렬처럼 하나하나 swap하지는 않을겁니다.

아래 과정을 차분히 보다보면 더 잘 이해됩니다.

삽입정렬 수행과정

1. 현재 index에 있는 값을 선택합니다.
2. 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색합니다.
3. 삽입 위치부터 index에 있는 위치까지 shift 연상을 수행합니다.
4. 삽입 위치에 선택한 데이터를 삽입하고 index++ 연산을 수행합니다.
5. 전체 데이터의 크기만큼 index가 커질 때까지, 즉 더는 선택할 데이터가 없을 때까지 반복합니다.

버블, 선택, 삽입정렬은 최선의 경우 또한 Ω(n**2)이다

list가 [1, 2, 3, 4, 5, 6, 7, 8]로 완전하게 정렬되어있다 하더라도,

사람이 볼 때는 직관적으로 정렬이 되어있다는 것을 알 수 있습니다.

하지만 컴퓨터의 입장에서는 정렬이 안되어있다고 가정하고, 모든 과정을 반복하여 수행, 확인하기 때문입니다.