keehyun2

void bucketSort(int[] a, int maxVal) {
  int [] bucket=new int[maxVal+1];

  for (int i=0; i<bucket.length; i++) {
    bucket[i]=0;
  }

  for (int i=0; i<a.length; i++) {
    bucket[a[i]]++;
  }

keehyun2

void radixSort(int[] arr) {
  int[] result = arr ;
  for (int place = 1; place <= 1000000000; place *= 10) {
    result = countingSort(result, place);
  }
  for (int i = 0; i < arr.length; i++) {
    arr[i] = result[i]; 
  }
}

keehyun2

void countingSort(int[] arr) {
  int n = arr.length;

  int output[] = new int[n]; // 결과를 저장할 임시 배열

  int count[] = new int[256]; // arr 에 정수 입력값중에 255 를 넘어가는 건 정렬되지 않습니다...

  for (int i = 0; i < n; ++i)
    ++count[arr[i]]; // 계수 를 측정합니다. 

keehyun2

/**
* heap 정렬을 합니다. 
* @param arr
*/
void heapSort(int[] arr) {
  for (int i = (arr.length - 1) / 2 ; i >= 0; i--) 
    heapify(arr, i, arr.length); // 모든 내부 node를 index가 큰 node 부터 root node(arr[0])까지 히프화합니다. 
  // arr[0](root node)에는 최댓값이 들어가고 모든 서브트리가 heap 이됩니다. 
  for (int j = arr.length - 1; j > 0; j--) {
    swap(arr, 0, j); // 0번 원소와 j번 원소를 교환합니다.

keehyun2

/**
* 비순환 드라이버 method
* @param arr
*/
void quickSort(int[] arr) {
  quickSort(arr,0,arr.length);
}
	
/**
* 퀵 정렬

keehyun2

/**
* 비순환 드라이버 method
* @param arr
*/
void mergeSort(int[] arr) {
  mergeSort(arr,0,arr.length);
}

/**
* 합병 정렬 - 분할하는 로직이 들어있고, 다른 합병정렬 알고리즘을 가지고 있는 함수를 실행합니다.

keehyun2

/**
* 셸 정렬에 의해 나누어진 부분 배열을 정렬할 삽입 정렬 알고리즘 
* @param array 배열
* @param startIndex 시작 인덱스
* @param gap 증분 
*/
void customInsertionSort(int[] arr, int startIndex, int gap) {
  for(int i = startIndex + gap; i < arr.length; i+=gap) { 
    // 삽입정렬과 다르게 i가 startIndex + gap에서 시작하고 증분이 1이 아니고, gap이 된다.
    int ai = arr[i];

keehyun2

void insertionSort(int[] arr){
  for(int i = 1; i < arr.length; i++) { 
    // i가 0이 아니라 1부터 시작합니다. i가 0인 loop 는 비교할 원소가 없습니다.
    int ai = arr[i]; // 정렬된 앞 배열에 삽입될 원소, 위치를 찾을 때까지 임시저장.
    int j; // 비교 연산 및 이동 연산을 한 임시 변수
    for (j = i; j > 0 && arr[j-1] > ai; j--) // 정렬된 배열에서 ai 보다 큰 값이 나올 때까지 j 감소
      arr[j] = arr[j - 1]; // 원소가 한 칸씩 우측으로 이동
    arr[j] = ai;  // 마지막으로 나온 j에 ai 를 삽입
  }
}

keehyun2

void selectionSort(int[] arr){
  for(int i = arr.length - 1; i > 0; i --) {
    int maxIndex = 0 ; // 배열 원소중 max 값의 index를 저장할 변수
    for(int j = 1; j <= i ; j++)
      if(arr[j] > arr[maxIndex]) maxIndex = j;
    swap(arr, maxIndex, i);
  }
}

keehyun2

void bubbleSort(int[] arr){
  for(int i = arr.length - 1; i > 0; i --)// main loop, i 는 (배열의 길이 - 1) 에서 1까지 1씩 감소
    for(int j =0; j < i ; j++)	// j 는 0부터 i 까지 1씩 증가하며 반복
      if(arr[j] > arr[j+1]) swap(arr, j, j+1); // index 가 작은 원소가 클경우 교환
}