NAIAHD

06-1 정렬

정렬은이름 , 학번, 키 등 핵심 항목의 의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다.

오름차순 ascending order 내림차순 descending order

정렬 알고리즘의 안정성

안정 된 정렬: 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말합니다.

안정되지 않은 알고리즘은 같은 점수인 경우 반드시 학번 순서대로 정렬되지는 않습니다.

내부정렬과 외부 정렬

정렬 알고리즘도 하나의 배열에서 작업할 수 있는 경우에는 내부 정렬 internal sorting

하나의 배열에서 작업할 수 없는 경우에는 외부 정렬 external sorting

정렬 알고리즘의 핵심 요소 

교환 , 선택 ,삽입

06-2 버블 정렬

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복합니다.

                                                                                                              ←----------------------------       

                                                                                      ←----------------------------  

static void swap(int[] a,int idx1,int idx2){

  int t = a[idx1];

  a[idx1] = a[idx2];

  a[idx2] = t;

}

static void bubbleSort(int[] a,int n){

  for(int i = 0; i< n-1;i++)

    for (int j = n-1; j>i ; j--)

      if (a[j-1] > a[j])

         swap(a, j-1,j);

}

알고리즘 개선

static void bubbleSort(int[] a,int n){

  for(int i = 0; i< n-1;i++){

    int exchg =0;

    for (int j = n-1; j>i ; j--)

      if (a[j-1] > a[j]){

        swap(a, j-1,j);

        exchg++;

      }

    if(exchg == 0) break;

  }

}

알고리즘 개선(2)

static void bubbleSort(int[] a,int n){

  int k = 0;

  while( k < n-1){ 

    int last = n-1;

    for (int j = n-1; j>i ; j--)

      if (a[j-1] > a[j]){

        swap(a, j-1,j);

        last= j;

      }

    k = last;

  }

}

06-3 단순 선택 정렬

가장 작은 요소부터 정렬하는 알고리즘이기 때문에 가장 작은 값의 요소인 1을 선택해 정렬을 시작합니다.

1을 6과 교환합니다.

static void selectoinSort(int[] a, int n){
  for(int i = 0; i< n-1; i++){
  	int min = i; //아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록합니다.
    for(int j = i+1; j <n;j++)
    	if(a[j] < a[min])
        	min = j;
    swap(a,i,min); //아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환합니다.
  }
}

06-4 단순 삽입 정렬

선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘입니다.

트럼프 카드를 한 줄로 늘어놓을 때 사용하는 방법과 비슷한 알고리즘입니다.

아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입힙니다.

static void insertionSort(int[] a, int n){
	for (int i = 1; i <n;i++){
    	int j ;
        int tmp = a[i];
        for (j = 1; j>0 && a[j-1] > tmp; j--)
        	a[j] = a[j-1];
        a[j] = tmp;
    }
}

06-5 셸 정렬

단순 삽입 정렬 :

장점:정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라집니다.

단점:삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아집니다.

단순 삽입 정렬의 장점은 살리고 단점은 보완한 정렬 알고리즘으로 도널드 셸이 고안했습니다. 먼저 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고 , 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법입니다.

static void shellShort(int[] a, int n){
	for (int h = n/2; h >0; h/=2)
    	for(int i = h; i<n;i++){
        	int j;
            int tmp = a[i];
            for(j = i-h; j>=0 && a[j] > tmp; j-=h)
            	a[j+h] = a[j];
            a[j+h] = tmp;
        }
}

증분값(h값)의 선택

h값은 n부터 감소시켜 마음에 1이 되면 됩니다. 

static void shellShort(int[] a, int n){
	int h ;
    for (h = 1; h < n /9; h = h * 3 + 1)
    ;
	for (; h >0; h/=3)
    	for(int i = h; i<n;i++){
        	int j;
            int tmp = a[i];
            for(j = i-h; j>=0 && a[j] > tmp; j-=h)
            	a[j+h] = a[j];
            a[j+h] = tmp;
        }
}

06-6 퀵 정렬

퀵 정렬은 일반적으로 사용되고 있는 아주 빠른 정렬알고리즘입니다.

피벗 pivot

pl

pr

static void quickSort(int[] a, int left, int right){
	int pl = left;
    int pr = right;
    int x = a[(pl+pr) / 2];
    
    do {
    	while(a[pl] < x) pl++;
        while(a[pr] > x) pr--;
        if(pl <= pr)
        	swap(a, pl++, pr--);
    }while(pl <= pr);
    
    if(left < pr) quickSort(a, left, pr);
    if(pr<ringht) quickSort(a, pl, right);
}

시간 복잡도 : O(n log n)

최악의 시간 복잡도 O(n^2)

06-7 병합 정렬

먼저 정렬마친 두 배열의 병합을 살펴보겠습니다. 각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬을 마치는 배열을 만듭니다.

//정렬을 마친 

static void merge(int[] a, int na,int[] b, int nb, int[] c){
	int pa = 0;
    int pb = 0;
    int pc = 0;
    
    while(pa<na&& pb <nb)
    	c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
        
    while(pa < na)
    	c[pc++] = a[pa++];
    
    while(pb < nb)
    	c[pc++] = b[pb++]
}

Arrays.sort로 퀵 정렬과 병합 정렬하기

06-8 힙 정렬

힙을 사용하여 정렬하는 알고리즘 입니다.

힙은 '부모의 값이 자식의 값보다 향상 크다'는 조건을 만족하는 완전이진트리입니다.

가장 큰 값이 루트에 위치

부모이 값 >= 자식의 값

힙 정렬

루트를 없애고 힙 상태 유지하기

루트 꺼냅니다. 그런 다음 비어 있는 루트 위치로 힙의 마지막 요소를 옮깁니다.

static void downHeap(int[] a, int left, int right){
	int temp = a[left];
    int child;
    int parent;
    
    for(parent = left; parent < (right+1)/2 ; parent = child){
    	int cl = parent * 2 +1;
        int cr = cl +1;
        child = (cr <= right && a[cr] > a[cl]) ? cr:cl;
        if (temp >= a[child])
        	breakl
        a[parent] = a[child];
    }
    a[parent] = temp;
}

static void heapSort(int[] a, int n){
	for (int i = (n-1) / 2 ; i >=0;i--)
    	downHeap(a,i,n-1);
        
    for(int i = n-1; i>0; i--){
    	swap(a, 0, i);
        downHeap(a,0,i-1);
    }
}

06-9 도수 정렬

도수 정렬 요소를 비교할 필요가 없다는 특징이 있습니다.

도수 정렬 알고리즘은 도수분포표 작성, 누적도수 분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어집니다.

도수분포표 작성:

각 점수에 해당하는 학생이 몇 명인지를 나타내는 도수분포표를 작성합니다.

누적도수 분포표 작성:

'0점 부터 점수 n까지 몇 명의 학생이 있는지 ' 누적된 값을 나타내는 누적도수분포표를 만든다..

목적 배열 만들기:

각각의 점수를 받은 학생이 몇 번쨰에 위치하느닞 알수 있으므로 이 시점에서 정렬은 거의 마쳤다고 할 수 있습니다.

배열 복사

정렬은 끝났지만 정렬 결과를 저장한 곳은 작업 배열입니다.

static void fSort(int[] a, int n, int max){
	int[] f = new int[max+1];
    int[] b = new int[n];
    
    for(int i = 0; i<n;i++) f[a[i]]++;
    for(int i = 1; i<=max;i++) f[i] += f[i-1];
    for(int i = n-1; i>=0;i--) b[--f[a[i]]] = a[i];
    for(int i = 0; i<n;i++) a[i] = b[i];
}

[출처] :Do it! 자료구조와 함께 배우는 알고리즘 java편