[알고리즘] 퀵정렬, 합병정렬 구현코드

[퀵정렬]

import java.io.*;
import java.util.*;

class Main {
    public static void main(String args[]) {
        // 정렬을 할 배열 array
        int[] array = {30, 1, 6, 19, 7, 9, 10};

        // 퀵 정렬 메서드 호출
        quickSort(array, 0, array.length - 1);

        // 정렬된 후 배열 출력
        System.out.println(Arrays.toString(array));
    }

    private static void quickSort(int[] array, int left, int right) {
        // 왼쪽 위치가 오른쪽의 위치보다 크거나 같을 경우 리턴
        if (left >= right) return;

        // 분할을 위한 피벗의 값을 구하기 위해 partition메소드 호출
        int pivot = partition(array, left, right);

        // 피벗을 기준으로 퀵 정렬 수행
        quickSort(array, left, pivot);
        quickSort(array, pivot + 1, right);
    }

    private static int partition(int[] array, int left, int right) {
        int lo = left - 1;
        int hi = right + 1;
        int pivot = array[(left + right) / 2];

        // lo가 hi보다 크거나 같을 경우 hi의 값을 리턴
        while (true) {
            // 왼쪽 인덱스가 피벗보다 값이 작을 경우 lo의 값을 증가
            do {
                lo++;
            } while (array[lo] < pivot);

            // 오른쪽 인덱스가 피벗보다 값이 크고, lo보다 클 경우 값을 감소
            do {
                hi--;
            } while (array[hi] > pivot && lo <= hi);

            // lo가 hi보다 크거나 같은 상황이 올 경우 hi를 리턴
            if (lo >= hi) {
                // 이게 분할을 위한 기준 피벗이 된다.
                return hi;
            }

            // 교환을 수행할 원소를 찾을 경우 swap함수 호출
            swap(array, lo, hi);
        }
    }

    // 두 값을 교환할 메서드 swap
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

[합병정렬]

import java.io.*;
import java.util.*;

class Main {
  public static void main(String args[]) { 
    // 정렬을 수행할 배열
    int[] array = { 230, 10, 60, 550, 40, 220, 20 };

    // MergeSort 메서드 호출 => 인자로 배열, 왼쪽, 오른쪽을 받는다.
    MergeSort(array, 0, array.length-1);

    // 정렬 후 배열
    System.out.println(Arrays.toString(array));
  }

  public static void MergeSort(int[] array, int left, int right) {
    if(left < right) {
      // 배열의 중간 값
      int mid = (left + right)/2;

      // 최소단위까지 쪼개기 위해 MergeSort호출
      MergeSort(array, left, mid);
      MergeSort(array, mid+1, right);

      // 정렬 후 합병을 위한 Merge호출
      Merge(array, left, mid, right);
    }
  }

  public static void Merge(int[] array, int left, int mid, int right) {
    System.out.println(Arrays.toString(array));
    int[] L = Arrays.copyOfRange(array, left, mid+1);
    int[] R = Arrays.copyOfRange(array, mid+1, right+1);

    // 정렬을 위한 변수
    int i = 0;
    int j = 0;
    int k = left;
    int ll = L.length;
    int rl = R.length;

    // i와 j가 L배열의 길이와 R배열의 길이보다 작을 경우 수행
    while(i < ll && j < rl) {
      // L배열에 있는 값이 R배열에 있는 값보다 작을 경우
      if(L[i] <= R[j]) {
        // 배열의 k위치에 L배열의 i번째 원소를 넣는다.
        array[k] = L[i++];
      }else {
        // 그 반대의 경우
        array[k] = R[j++];
      }
      k++;
    }

    // 위 조건을 벗어낫을 경우 둘 중 하나의 배열에 남은 원소는 큰 경우이므로 차례대로 넣어준다.
    while(i < ll) {
      array[k++] = L[i++];
    }

    while(j < rl) {
      array[k++] = R[j++];
    }
  }
}

[힙소트]

import java.io.*;
import java.util.*;

class Main {  
  public static void main(String args[]) {
    // 정렬을 위한 배열
    int[] array = {230, 10, 60, 550, 40, 220, 20};

    // 힙소트 메서드 호출
    heapSort(array);

    // 정렬 후 배열의 결과 값 출력
    System.out.println(Arrays.toString(array));
  }
  
  public static void heapSort(int[] array) {
    // 배열의 길이 n
    int n = array.length;

    
    for(int i = n/2-1; i>=0; i--) {
      System.out.println("i의 값:" + i);
      heapify(array, n, i);
    }

    for(int i = n-1; i > 0; i--) {
      System.out.println("i2의 값:" + i);
      swap(array, 0, i);
      heapify(array, i, 0);
    }
  }
  
  public static void heapify(int[] array, int n, int i) {
    int p = i;
    int l = i*2+1;
    int r = i*2+2;

    if(l < n && array[p] < array[l]) {
      p = l;
    }
    if(r < n && array[p] < array[r]) {
      p = r;
    }
    if(i != p) {
      swap(array, p, i);    
      System.out.println(Arrays.toString(array));
      heapify(array, n, p);
    }
  }

  public static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
  }
}