[자료구조] 정렬 (sorting) - 버블 ,선택, 삽입, 쉘 알고리즘

공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 

 

---

정렬의 개념

각 데이터를 특정 항목으로 오름차순 혹은 내림차순으로 재배열하는 작업을 말한다.

정렬의 종류

내부 정렬 : 삽입법, 교환법, 선택법, 병합법, 분배법 등 

데이터량이 적을 때 RAM과 같은 주기억장치에 정렬하는 방법을 말한다.

RAM은 속도가 빠른 대신에 용량이 작다. 

 

외부 정렬 : 밸런스 병합 정렬, 캐스케이드 병합 정렬, 폴리파즈 병합 정렬, 오실레이팅 병합 정렬 

대용량의 데이터를 HDD, SSD와 같은 보조기억장치에서 기억시켜서 정렬하는 방법을 말한다.

내부정렬과는 반대로 속도가 느린 대신 용량이 크다. 

 

컴퓨팅에서는 주기억장치가 

내부 정렬 : 버블 정렬

두 개의 데이터를 비교하여 크기에 따라 위치를 서로 교환하는 정렬 방식이다.

평균과 최악 모두 시간복잡도가 O(n^2)인 탓에 성능이 좋지는 않다.

 

ex : 8, 5 7, 2,4를 버블 정렬로 오름차순으로 정렬할 시 과정

 

초기값 :85724

 

 1) 58724 -> 57824 -> 57284 -> 57248

 2) 57248 -> 52748 -> 52478 

 3) 52478 -> 25478 -> 24578 

 4) 24578

 

내부 정렬 - 선택 정렬

N개의 데이터 중 최솟값을 찾아 첫 번재 위치에 놓고, 나머지 N-1개로 반복하여 정렬하는 방식이다.

평균과 최악 모두 시간복잡도가 O(n^2)인 탓에 성능이 좋지는 않다.

 

ex : 8, 5 7, 2,4를 선택 정렬 할 시 과정

 

초기상태 : 85724 

 

1) 58724 -> 58724 -> 28754 -> 28754

2) 28754 -> 27854 -> 24875

3) 24875 -> 24785 -> 24758 -> 24578

4) 24578 

내부 정렬 - 삽입 정렬 

순서화된 데이터에 새로운 데이터를 순서에 맞게 삽입하여 정렬하는 방식이다. 

삽입하는 방식 때문에 경우에 따라 정렬이 복잡해질 수 있다는 단점이 있으며

마찬가지로 평균과 최악 모두 시간복잡도가 O(n^2)인 탓에 성능이 좋지는 않다.

 

ex : 8, 5 7, 2,4를 버블 정렬로 오름차순으로 정렬할 시 과정

 

초기상태 : 85724 

 

1) 85724 -> 58724 : 두 번째 값을 첫 번째값과 비교하여 5를 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동

2) 58724 -> 57824 

3) 57824 -> 25784 

4) 25784 -> 24578 

내부 정렬 - 쉘 정렬

삽입 정렬이 어느 정도 정렬된 배열엥서 빠르다는 특징에서 착악된 삽입 정렬의 확장 기법으로

평균 시간 복잡도는 O(n^ 1.5), 최악 시간복잡도는 O(n^2)이다. 

결국 삽입 정렬인 이 최악의 경우에는 많은 이동이 필요하기 때문이다. 

 

 

참고자료

https://youtu.be/Rvyl1KG7O7s?si=LXY5ksuIdM202akd