[Algorithm] Sorting (Selection, insertion)

[스터디원 준비 자료]

알고리즘, 의사코드, 선형탐색 : cs50-2장 알고리즘,의사코드,선형탐색

버블 정렬 : Bubble Sort

합병 정렬 : 합병 정렬

이진 탐색 : https://www.icloud.com/iclouddrive/0q7RwpA9Y7oRVkF5f2Sq_BmtA

---

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

 

프로그램에서 데이터 가공시 오름차순, 내림차순 등의 정렬을 사용하는 경우가 많다

(가장 많이 사용되는 알고리즘 중 하나)

 

정렬은 알고리즘의 효율성을 쉽게 이해할 수 있기 때문에, 초반에 알고 가면 좋다

(일종의 공식처럼 사용되는 경우가 많기 때문에, 효율적인 정렬 알고리즘을 알고 있는 것이 중요)

 

선택 정렬

데이터가 무작위로 있을 때, 이 중 가장 작은 데이터를 선택해 가장 앞에 있는 데이터와 위치를 변경,

이후 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 위치를 변경하며 바꾸는 과정을 반복한다

이렇게 "가장 작은 것을 선택"하며 인덱스를 전체 순회하게 되는 것이 선택 정렬 알고리즘이다

위와 같은 방식으로 첫 번째 인덱스부터 마지막 인덱스까지 전체 순회하며 하나씩 위치를 변경한다

 

마지막 인덱스까지 순회하면 결과적으로 위와 같이 정렬이 되는 것을 확인할 수 있다

 

 

[선택 정렬의 시간 복잡도]

N - 1번 만큼 가장 작은 수를 찾아서 가장 앞으로 보내야 한다

매번 가장 작은 수를 찾기 위해 비교 연산 과정이 필요하다

 

빅오 표기법으로는 O(N²)이라고 표현할 수 있다

 

* 선택 정렬의 경우 순회해야 할 인덱스의 수가 커지면 커질수록 비효율적으로 시간이 증가하게 된다

 

---

삽입 정렬

삽입 정렬 또한 선택 정렬과 마찬가지로 동작 원리를 직관적으로 알기 쉬운 알고리즘으로,

선택 정렬보다는 실행 시간 측면에서 더 효율적인 알고리즘이다

 

특히 삽입 정렬은 필요할 때만 위치를 변경하며, 특히 데이터가 거의 정렬 상태와 흡사하다면 굉장히 효율적이다

(선택 정렬은 무조건 모든 인덱스를 순회하며 비교하는 반면, 삽입 정렬은 그렇지 않다)

 

선택 정렬은 항상 두 번째 데이터부터 순회를 시작하는데, 첫 번째 데이터는 그 자체로 정렬됐다고 판단하기 때문

첫 번째 인덱스를 기준으로 정렬되어야할 인덱스의 값이 첫 번째 인덱스보다 큰 값인지 작은 값인지를 비교,

정렬되어있는 인덱스의 값보다 값이 작다면 왼쪽, 크다면 위치 변경없이 그대로 하나씩 비교하며 순회한다

순회 과정은 아래와 같다

위와 같은 방식으로 모든 해당 값이 큰 값인지, 작은 값인지를 기준하기 때문에 전체 인덱스를 비교하진 않는다

 

결과적으로 위와 같이 정렬이 되는 것을 확인할 수 있다

 

 

[삽입 정렬의 시간 복잡도]

삽입 정렬의 시간 복잡도는 O(N²)으로, 선택 정렬과 동일한 시간 복잡도를 가진다

실제 수행 시간을 테스트해보면 선택 정렬과 비슷한 시간이 소요됨을 확인할 수 있다

 

위에서 언급한 바와 같이 데이터가 이미 거의 정렬된 상태라면 퀵 정렬보다도 빠른 효율을 보여준다

(일반적으로는 비효율적 정렬 알고리즘에 속한다, 선택 정렬도 포함)

 

---

선택 정렬과 삽입 정렬의 예시

하나의 수열에 다양한 수가 존재하며, 수는 크기에 상관없이 나열되어 있다

이 수를 큰 수부터 작은 수의 순서로 정렬해야 할 때, 내림차순으로 정렬하는 프로그램을 작성

 

[입력]

첫째 줄에 수열에 속해 있는 수의 개수 N

둘째 줄부터 N + 1번째 줄까지 N개의 수를 입력

 

[출력]

입력으로 주어진 수열이 내림차순으로 정렬된 결과를 출력

 

[선택 정렬]

 

 

[삽입 정렬]

 

* 파이썬에서 기본적으로 제공해주는 sort, sorted를 사용하는 것이 훨씬 효율적이지만

  이해에 대한 확인, 직접적인 구현을 위해 작성 된 코드입니다