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편

탐색은 : 여러 개의 자료 중에서 원하는 것을 찾아내는 것

정렬은 : 주어진 자료를 순서에 맞춰 나열하는 것

07. 순차 탐색 

주어진 리스트에 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘

sequential search

1. 순차 탐색으로 특정 값의 위치 찾기

def search_list(a, x):

  n = len(a)

  for i in range(0,n):

     if x == a[i]:

        return i

  return -1

2. 알고리즘 분석

계산 복잡도 O(n)

08. 선택 정렬

1. 선택 정렬로 줄 세우기

2. 쉽게 설명한 선택 알고리즘

def find_min_idx(a):

   n = len(a)

   min_idx = 0

   for i in range(1, n):

      if a[i] < a[min_idx]:

         min_idx = i

   return min_idx

def sel_sort(a):

  result = []

  while a:

     min_idx = find_min_idx(a)

     value = a.pop(min_idx)

     result.append(value)

  return result

3. 일반적인 선택 알고리즘

def sel_sort(a):

  n = len(a)

  for i in range(0,n-1):

    min_idx = i

    for  j in range(0,n-1):

      if a[j] < a[min_idx]:

         min_idx = j

  a[i], a[min_idx] = a[min_idx], a[i]

4. 알고리즘 분석

O(n^2)

09. 삽입 정렬 

리스트 안의 자료를 작은 수 부터 큰 순서로 배열하는 정렬 알고리즘

1. 삽입 정렬로 줄 세우기

2. 쉽게 설명한 삽입 정렬 알고리즘

def find_ins_idx(r, v):

  for i in range(0, len(r)):

     if v < r[i] :

       return i

  return len(r)

def ins_sort(a):

  result = []

  while a:

    value = a.pop(a)

    ins_idx = find_ins_idx(result , value)

    result.insert(ins_idx , value)

  return result

3. 일반 적인 삽입 정렬

def ins_sort(a):

  n = len(a)

  for i in range(1, n):

    key = a[i]

    j = i-1

    while j >= 0 and a[j] < key:

       a[j+1] = a[j]

       j -= 1

    a[j+1] = key

4. 알고리즘 분석 

O(n^2)

문제 10 : 병합 정렬

리스트 안의 자료를 작은 수부터 큰 수 순서로 배열하는 정렬 알고리즘을 만들어 보세요.

1. 병합 정렬로 줄 세우기

2. 쉽게 설명한 병합 정렬 알고리즘

def merge_sort(a):

  n = len(a)

  if n <= 1:

    return a

  mid = n //2

  g1 = merge_sort(a[:mid])

  g2 = merge_sort(a[mid:])

  result = []

  while g1 and g2:

    if g1[0] < g2[0]:

      result.append(g1.pop(0))

    else:

      result.append(g2.pop(0))   

    while g1:

      result.append(g1.pop(0))

    while g2:

      result.append(g2.pop(0))

  return result

3. 병합 정렬에서의 재귀 호출

4. 일반적인 병합 정렬 알고리즘 

def merge_sort(a):

  n = len(a)

  if n <= 1:

    return

  mid = n //2

  g1 = a[:mid] 

  g2 = a[mid:]

  merge_sort(g1)

  merge_sort(g2 )

  i1 = 0

  i2 = 0

  ia = 0

  while i1< len(g1) and i2< len(g2):

    if g1[i1] < g2[i2]:

      a[ia] = g1[i1]

      i1 += 1

      ia += 1

    else:

      a[ia] = g2[i2]

      i2 += 1

      ia += 1

  while i1< len(g1):

      a[ia] = g1[i1]

      i1 += 1

      ia += 1

  while i2< len(g2):

      a[ia] = g1[i2]

      i2 += 1

      ia += 1

  5. 알고리즘 분석

문제 11. 퀵정렬

그룹을 둘로 나눠 재귀 호출하는 방식

def quick_sort(a):

  n = len(a)

  if n <=1:

    return a

  pivot = a[-1]

  g1 = []

  g2 = []

  for i in range(0,n-1):

    if a[i] < pivot:

      g1.append(a[i])

    else:

      g2.append(a[i])

  return quick_sort(g1)+[pivot] + quick_sort(g2)

def quick_sort_sub(a, start, end):

  if end - start <= 0:

     return 

  pivot = a[end]

  i = start

  for j in range(start, end):

    if a[j] <= pivot:

      a[i], a[j] = a[j] , a[i]

      i+=1

  a[i],a[end] = a[end],a[i]

  quick_sort_sub(a, start, i-1)

  quick_sort_sub(a, i+1, end)

def quick_sort(a):

  quick_sort_sub(a, 0, len(a)-1)

문제 12. 이분 탐색

둘로 나눈다 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳만 탐색하기 때문에 자료를 하나하나 찾아야 하는 순간 탐색보다 원하는 자료를 훨씬 빨리 찾을 수 있습니다.

def binary_search(a, x):

  start = 0

  end = len(a) -1

  while start <= end:

    mid = (start+end)//2

    if x == a[mid]:

      return mid

    elif x > a[mid]:

      start = mid +1

    else:

      end = mid-1

  return -1

출처 : 모두의 알고리즘 with 파이썬