알고리즘 자료구조 - 6

6장

 

** 정렬알고리즘의 시간복잡도

 - https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 - https://ko.wikipedia.org/wiki/%EC%A0%95%EB%A0%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

1)

정렬(sorting) : 핵심 항목(key)의 대소관계에 따라 데이터 집합을 일정한 규칙으로 늘어서도록 바꾸는 작업

오름차순 정렬(ascending order) : 작은 데이터에서 큰 데이터 순으로 정렬

내림차순 정렬(descending order) : 큰 데이터에서 작은 데이터 순으로 정렬

 

 

2)

내부 정렬(internal sorting) : 하나의 배열 내에서 데이터를 정렬할 수 있을 경우 사용하는 알고리즘

외부 정렬(external sorting) : 하나의 배열 내에서 데이터를 정렬할 수 없을 경우 사용하는 알고리즘

 

안정 정렬(stable sort)과 불안정 정렬

 - 안정 정렬 : 키 기준 같은 값을 가진 데이터(행)를 정렬시 이전 순서와 동일한 순서로 정렬되는 방식

 ** 보통 표에서 중요하다. 예를 들어, 이름-생일 형태의 표가 있다면,

    키값을 이름으로 하여 정렬하고 동일한 이름이 나왔을 경우, 안정 정렬을 수행할 경우는 원본 표에서 저장된 생일 순서가 변하지 않는다.

    즉, 생일 정렬 -> 이름 정렬 순서로 정렬시 이전의 생일 순서로 정렬된 내용이 남아있을 수 있다.(사용자 입장에서 사용하기 편하다)

 

** 안정정렬관련 설명

 - https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-3  

 

3)

정렬 알고리즘의 핵심요소 : 교환, 선택, 삽입

 ** 대부분의 정렬 알고리즘은 위의 핵심요소를 응용

 

4)

버블 정렬(bubble sort)

 - 이웃한 두 요소의 데이터의 대소 관계를 비교하여 교환을 반복하는 알고리즘

 - 액체안의 공기방울이 표면으로 올라오는 모습에서 명명됨

 - 패스(pass) : 데이터의 비교, 교환작업을 하는 1번의 루프를 의미

 

기본

 - 데이터가 들어있는 배열(n개의 요소, n개의 데이터)의 끝부터 시작까지 n:n-1 비교 및 교환

 - 반복

 - 다음 차례에서는 끝부터 시작-1까지 비교 및 교환

 - 위의 과정을 끝부터 끝-1까지 반복

 - 모든 정렬이 끝나려면 n-1회의 패스가 수행되어야 함

 

 - 구현시에는 1개의 데이터를 배열에 정렬시키기 위한 과정을 n-1회 반복하기 위한 변수(i, 0부터 n-1까지 증가)

   주어진 요소 범위의 데이터끼리를 비교하기 위한 변수(j, n-1부터 i까지 감소)가 필요하다

 

 

개선1

 - 정렬을 하던 도중 1번의 루프과정에서(패스에서) 배열의 데이터가 한번이라도 교환이 이루어지지 않으면 해당 배열은 정렬이 끝났는 것을 알 수 있다

 - 즉, 매 루프(패스)별 교환여부를 체크하는 변수를 추가

 

 

 

개선2

 - 한번의 패스내에서 임의의 요소 이후 데이터 교환이 이루어지지 않는다면 해당 요소 이후부터는 정렬되었음을 알 수 있다

 - 즉, 교환이 이루어지는 요소를 기억하는 변수를 추가

 - 패스의 숫자가 줄어들기 때문에 for문이 아닌 while문을 사용하며, 조건에 위의 변수를 넣는다

 

 

5)

단순선택 정렬(straight selection sort)

 - 가장 작은 데이터의 요소부터 선택해 알맞은 위치로 옮겨 정렬하는 알고리즘

 - 배열에서 가장 작은 데이터를 가지는 요소를 구해 배열의 n-n요소의 데이터와 교환

 - n-2까지 저장할 요소를 증가시키며 정렬

 

6)

단순삽입 정렬(straight insertion sort)

 - 선택한 데이터가 위치한 요소보다 더 앞쪽의 요소의 데이터와 비교하여 삽입하는 작업을 반복하는 알고리즘

 - 만약 내림차순으로 정렬한다면, n번째 요소의 데이터를 따로 저장, n번째 데이터와 n-1번째 데이터를 비교, n-1번째 요소의 데이터가 n번째 요소의 데이터보다 크다면 n-1번째 요소의 데이터를 n번째 요소의 데이터가 위치한 요소에 저장

                                 n번째 요소의 데이터보다 작은 데이터가 발견되면 해당 데이터가 저장된 요소+1 위치에 n번째 요소의 데이터값 저장

 

 

 

** 버블, 선택, 삽입정렬은 단순 정렬이며, 시간복잡도는 모두 O(n^2)이다(낮은 효율)