정렬(Sorting)#1

정렬(Sotring)

 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것으로 순서에는 오름차순(Ascending Order)과

내림차순(Descending Order)이 있다.

 데이터를 정렬해야 하는 이유는 탐색의 효율성을 위해서이다.

 

 

레코드(Record)

정렬 시켜야 할 대상, 즉 데이터

 

 

키(Key)

특정한 레코드를 식별해주는 역할을 하는 필드

 

 

정렬 알고리즘의 분류

정렬이 수행되는 장소에 따라 내부 정렬과 외부 정렬로 구분된다.

 

 

정렬 장소에 따른 분류

 

내부 정렬(Internal Sorting)

정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬

 

외부 정렬(External Sorting)

외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려놓은 상태에서 정렬을 수행하는 정렬, 대용량 자료의 정렬에 적합

 

 

구현 복잡도와 효율성에 따른 분류

단순하나 비효율적인 정렬: 삽입 정렬, 선택 정렬, 버블 정렬 등복잡하나 효율적인 정렬: 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬 등

 

 

정렬의 종류

 

선택 정렬(Selection Sort)

전체 숫자들 중 가장 작은 숫자를 반복해서 선택하여 앞으로 옮기는 방법을 사용하는 정렬 알고리즘

C에서 선택 정렬의 구현

시간 복잡도: O(n^2)

 

삽입 정렬(Insertion Sort)

정렬이 안 된 부분에서 하나를 뽑아 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복하는 정렬 알고리즘

C에서 삽입 정렬의 구현

시간 복잡도: O(n^2)

 

버블 정렬(Bubble Sort)

인접한 두 개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 비교-교환 방식의 정렬 알고리즘

C에서 버블 정렬의 구현 / 교환이 이루어지지 않으면 정렬이 완료된 것이므로 break하도록 했다면 메모리를 더 아낄 수 있었을 것 같다

시간 복잡도: O(n^2)