복잡하지만 효율적인 정렬알고리즘
1.힙정렬
:힙의 특성을 활용하여 정렬하는 알고리즘
:힙의 루트 노드에 저장된 값이 가장 커야한다.
:힙 관련 포스트 이용해서 자세하게
2.병합정렬
=>병합정렬은 데이터가 1개만 남을때까지 분할을 한다.
그리고 실제 정렬은 나눈것을 병합하는 과정에서 이루어진다.
*성능 평가
:비교연산과 이동연산이 실제 정렬을 진행하는 Mearge TwoArea함수 중심으로 진행된다.
:그래서 Mearge TwoArea 기준으로 시간복잡도를 계산해야한다.
:정렬의 우선순위를 비교하는 비교연산이 중심이므로, 비교연산 횟수를 계산한다.
데이터수가 8개일때 병합의 과정은 3회 진행되었다.
마찬가지로 데이터수가 16개일때 병합의 과정은 4회 진행된다.
즉 데이터 수 n과 그에 따른 병합과정의 횟수 K에는 다음식이 성립된다.
****K=log2n이다
하지만
->임시배열에 저장된 데이터를 전부 원하는 위치로 옮기는 과정에서, 임시데이터를 병합하는 과정에서 이동연산이 2*n 이 이루어진다 .
그렇기때문에 빅오 연산은 O(N*log2n)이 된다
<소스>
3.퀵정렬
=>분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
정의: 퀵정렬은 정렬할 전체 원소에 대해서 정렬을 수행하지 않는다.
먼저 기준 값을 중심으로 전체 원소들을 왼쪽 부분집합과 오른쪽 부분집합으로 분할(Divide)한다.
왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고,
오른쪽 부분 집합에는 기준 값보다 큰 원소들을 이동시킨다.
근데 위 사진에서 pivot 설정이 가장 왼쪽으로 진행되는데 pivot설정을 데이터기준의 중간값으로
설정하는것이 좋다.
예 >왼쪽을 pivot으로 계속 설정한다면 최악의 경우
1 2 3 4 5 6 7 8 9
시간복잡도 O(nΛ2)이가 된다. ㅜㅜ
pivot을 mid로 하여 결정할때 : 분할횟수,이동연산 포함하면
분할정복처럼 O(N*log2n)
4.기수정렬
*기수 정의 :주어진 데이터를 구성하는 기본요소
예)2진수는 0과 1의 조합으로 데이터 표현하니깐 2진수의 기수는 0과 1이 기수
예)10진수는 0부터 9까지의 숫자조합으로 데이터 표현하니까 0~9까지의 숫자가 기수
기수정렬: 기수를 이용해서 정렬을 진행하는방식
[특징]
1.비교연산을 하지않고서 정렬하는 방법
2.정렬 알고리즘의 이론상 성능의 한계는 O(N*log2n)으로 알려져 있는데 ,기수정렬은 이러한 한계를 넘어설수있는 유일한 알고리즘 (하지만, 단점이 존재 -> 적용할수있는 범위가 제한적이다, "데이터의 길이"기 같은 대상으로만 정렬 가능)
1> LSD(Least Significant Digit) 기수정렬
="덜 중요한 자릿수"에서부터 정렬을 진행해 나간다는 의미
예를들어> 324와 421을 대소를 비교할때 3과 4만 보고 421이 크다고 판단을 해버리면 정렬이 진행되지않기때문에 , **대소 비교에 있어서 영향력이 가장 작은 자릿수부터 비교하는것
[단점]
작은 자릿수에서 시작해서 가장 큰 자릿수까지 모두 비교를 해야 값의 대소를 판단할수 있다.
비교중간에 대소를 판단하는 것이 불가능하기때문에 마지막까지 결과를 모른다는것이 단점
하지만, 이러한 단점이 프로그래밍을 하는데에서는 장점이 된다.
2> MSD(Most Significant Digit) 기수정렬
="가장 중요한 자릿수"에서부터 정렬을 진행해 나간다는 의미
=>LSD는 마지막에 가서 정렬순서를 판단하는 방식인 반면, MSD는 점진적으로 정렬을 완성해가는 방식 이다. 그래서 큰 장점은 끝까지 가지않아도 정렬이 완료될수 있다는 것이다.
224 ,232의 정렬순서는 이미 두번째 과정에서 판별이 났다.
두번째 자리수가 2가 3보다 앞서기때문!! 그래서 그결과는 세번째 자릿수에 영향을 받지않는다.
이러한 오류를 범하지 않으려면, MSD방식에서는 중간에 데이터를 점검해야한다.!!
[기수정렬 성능평가]
기수정렬은 비교연산이 핵심이 아니다.
오히려, 버킷으로의 데이터의 삽입과 추출이 핵심이다.
따라서 정렬의 시간복잡도는 삽입과 추출의 빈도수를 대상으로 결정해야한다.
정렬대상수가 n이고, 모든 정렬대상의 길이가 L이라고 할때, 시간 복잡도에 대한 기수정렬의 빅오는 O(ln )-> 이는 O(N)으로 보아도 된다.
일반적으로, "기수정렬"이라고 하면 LSD방식을 기준으로 이야기한다.
왜냐하면, 구현의 편의성 때문에!!
성능도 MSD와 LSD의 빅오는 같다.
[LSD기준 구현]
->버킷은 그 구조가 큐에 해당하기때문에, 큐를 활용해서 구현하는 경우도 있다고한다.
