외부정렬
하드디스크를 이용하여 자료를 정리한다.
속도는 느리지만
순차정렬
순차적으로 맨 앞에서부터 채워나간다.
작은숫자부터 앞에서 채워나가고 싶다고 한다면 (312 -> 123 순으로)
맨앞자리에 가장작은 숫자를 넣고 그다음 두번째 자리에 가장작은숫자를 넣고 그다음 세번째 자리에 가장작은 숫자를 넣는다.
이를 위한 알고리즘은 맨첫번째 자리와 두번째,세번째...가면서 자기보다 작은 숫자를 찾는다.
그리고 그수를 바꾼다.
바뀐수는 또다시 두번째, 세번째중 자기보다 작은수를 찾는다...
쭉하다 어떤 수 부터는 자기자신과 바뀌는 수가 없을것이다.
그러면 그때 끝이 난다.
이런식으로 두번째 세번째 쭈욱 해준다.
즉 i번째 숫자! 라는 key를 갖고 쭈우우욱 비교!
선택정렬
선택정렬은 해당자리에 가장 알맞은수를 찾아 넣는것이다.
즉 1,2,3,4,5 순으로 배치하고 싶다면 첫번째 자리에 가장 알맞은 자리 숫자 1을 찾는다.
3,4,1,5,2 --> 이런 순으로 있다면 int minimum을 선언하여 가장 작은 숫자 1을 찾아 minimum에 넣어주고 이를 첫번째 자리에 넣어준후 첫번째 자리 숫자를 기존 1이 있던 자리에 넣어준다.
즉 이는 5번만 수행하여 각자리에 알맞은 숫자를 넣어준다.
버블정렬
짝을지어 확인하는 방법이다. 예를 들어
32145 가 있으면 두개씩 짝짓는다고 할때 32가 일단 짝지어질 것이다.
그러면 2가더 작으니 32가 23이 된다. 이제 배열은 23145가 된다.
그다음 31을 짝짓는다. 그러면 1이 더 작으니 21345 가 된다.
그다음 34를 짝짓는다. 안바뀐다. 그다음 45를 짝짓는다. 안바뀐다.
즉 이런식으로 하면 맨뒤에 부터 내가 원하는 자릿수가 체워진다.
이번에는 짝짓는것을 21->12. 23. 34 -> 이렇게 네번만 짝지으면 된다.
이런식으로 짝짓기를 한턴 할때마다 맨뒤에 가장 큰수가 채워진다.
그리고 짝짓는 횟수는 한번씩 줄어들게 된다.
삽입정렬
비효율적이지만 대용량에 유리한 정렬이다.
설명 1.
3105에서 맨처음 <31>을 본다. 1은 이중에 자기의 자리인 첫번째 자리로 가고 3은 밀린다.
<13>이 된다. <130>을 본다. 0은 앞의 13 중 자기가 들어갈 자리를 본다. 첫번째 자리로 가고 13은 밀려서 013이 된다.
<0135>는 그대로 이다.
설명 2.
3105 에서 범위를 <31>로 하여 맨처음 31을 짝짓는다. 13이 된다.
그다음 범위를 <130>로하여 뒤에서부터 30을 비교. 0이 더작으니 앞으로 간다.
<103>에서 10을 비교. 0 이 더 작으니 앞으로 간다. <013>
그다음 범위를 <0135>로 한다. 그리고 35->13->01을 비교한다.
퀵정렬
퀵정렬은 재귀함수의 특성을 이용한다.
방법은 다음과같다.
31762 가 있다. 12367을 만들어 보자.
<3>1762 --> 이렇게 맨앞자리(굳이 맨앞이 아니여도됌) 를 기준으로 잡는다.
그리고 왼쪽부터 3보다 큰값이 있는지 확인한다. 그리고 오른쪽부터 3보다 작은값을 찾는다.
7을 찾고 2를 찾았다. 그럼 바꾸어준다.
<3>1267 이 된다.
그리고 왼쪽부터 3보다 작은값, 오른쪽부터 3보다 큰값을 찾는다. 이때 2까지는 3보다 작은값, 그리고 6까지는 3보다 큰값에 해당된다. 즉 내가 원하는 3보다 큰값, 우측부터 3보다 작은값을 못찾았다. 이런경우 교차한다 하며 이는 내림차순이므로 왼쪽값인 2를 기준으로 넣어준다.
<2>1367 이 된다.
이제 왼쪽부터 2보다 큰값, 우측부터 2보다 작은값을 찾아보자.
이번에도 동시에 만족하는것을 찾지못하고 1에서 교차가 일어난다.
그러면 기준은 1이되어 <1>2367이 된다.
더이상 교차는 없다. 그럼 끝이다.
이를 재귀함수로 부르는 것이 퀵정렬이다.
만족한다.
그러면 가운대에 2를 3대신 넣는다.
<2>1367 이 된다.
이제 왼쪽부터 2보다 큰값, 오른쪽부터 2보다 작은값을 찾는다.
`` 참고
https://www.youtube.com/watch?v=agfEj9_0k00
``
쉘정렬
0435792861 이런식으로 있다면 배열의길이인 10 /2 를 한다 . 5이다.
5를 간격으로 삽입정렬을 통해 배열을 나열한다.
그다음 5/2인 2를 통해 2를 간격으로 삽입정렬을 통해 배열을 나열한다.
2/1인 1을 간격으로 삽입정렬을 통해 배열을 나열한다.