정렬 알고리즘

선택 정렬

시간복잡도
O(N^2)

  public class SelectionSort {

 int idx, min, tmp;
 int cnt = 10;
 int[] array = {1, 10, 5, 8, 7, 5, 4, 3, 2, 9};

 public void execute() {
    for(int i = 0; i < cnt; i++) {
       min = i;
       for(int j = i+1; j < cnt; j++) {
          if(min > array[j]) {
             min = array[j];
             idx = j;
          }
       }
       tmp = array[i];
       array[i] = array[idx];
       array[idx] = tmp;
    }

    for(int i=0; i < cnt; i++)
       System.out.print(array[i] + " ");
 }
}

삽입 정렬

시간복잡도
O(N^2)
정렬된 상태에서 빠르다.

public class InsertionSort {
  int i, j, tmp;
  int[] array = {1, 10, 9, 4, 6, 8, 7, 5, 3, 2};
  public void execute() {
      for(i = 0; i < 9; i++) {
          j=i;
          while(array[j]>array[j+1]) {
              System.out.print("j:" + j + ":" + array[j]);
              System.out.println();
              System.out.println("j+1:" + j + ":" + array[j+1]);
              tmp = array[j];
              array[j] = array[j+1];
              array[j+1] = tmp;
              j--;
              if(j<0)
                  break;
          }
      }
      for(i = 0; i < 10; i++) {
          System.out.print(array[i] + " ");
      }
  }
}

계수 정렬

시간복잡도
O(N)

연속된 숫자

public class CountingSort {
 static int[] arr = { 1, 3, 5, 4, 3, 2, 5, 4, 3, 2,
         1, 2, 3, 1, 4, 5, 3, 2, 5, 4,
         3, 2, 5, 4, 3, 2, 3, 5, 4, 4,
         3, 2, 5, 4, 3, 0, 3, 5, 4, 4,
         3, 2, 5, 4, 3, 2, 3, 5, 4, 4,
         3, 2, 5, 4, 6, 0, 3, 5, 4, 4,
         1, 3, 5, 4, 6, 2, 5, 4, 3, 2,
         1, 3, 5, 4, 6, 2, 5, 4, 3, 2,
         1, 3, 5, 4, 3, 2, 5, 4, 3, 2,
         1, 3, 5, 4, 3, 2, 5, 4, 3, 2};
 static int number = 31;
 public void main() {
     int[] counting = new int[7]; //0~7까지 갯수를 담는 배열
     int[] results = new int[100]; //결과

     for(int i = 0; i < arr.length; i++) {
         counting[arr[i]]++;
     }
     for(int i = 0; i < counting.length; i++) {
         if(counting[i] != 0) {
             for(int j = 0; j < counting[i]; j++)
                 System.out.print(i);
         }
     }
 }
}

무작위 숫자

public class CountingSort {
 static int[] arr = { 1, 3, 5, 4, 3, 2, 5, 4, 3, 2,
         1, 2, 3, 1, 4, 5, 3, 2, 5, 4,
         3, 2, 5, 4, 3, 2, 3, 5, 4, 4,
         3, 2, 5, 4, 3, 0, 3, 5, 4, 4,
         3, 2, 5, 4, 3, 2, 3, 5, 4, 4,
         3, 2, 5, 4, 6, 0, 3, 5, 4, 4,
         1, 3, 5, 4, 6, 2, 5, 4, 3, 2,
         1, 3, 5, 4, 6, 2, 5, 4, 3, 2,
         1, 3, 5, 4, 3, 2, 5, 4, 3, 2,
         1, 3, 5, 4, 3, 2, 5, 4, 3, 2};
 static int number = 31;
 public void main() {
     int[] counting = new int[7]; //0~7까지 갯수를 담는 배열
     int[] results = new int[100]; //결과

     for(int i = 0; i < arr.length; i++) {
         counting[arr[i]]++;
     }
     //누접 합 더하기 1부터 시작
     for(int i = 1; i < counting.length; i++) {
         counting[i] += counting[i - 1];
     }
     for(int i = arr.length - 1; i >= 0; i--) {
         int value = arr[i];//원소값
         counting[value]--;//원소값 카운트 -1
         results[counting[value]] = value;//카운팅 순서에 원소값을 저장
     }

     for(int i = 0; i < results.length; i++) {
         if(i%10 == 0) System.out.println();
         System.out.print(results[i] + " ");
     }
 }
}