Java/선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬

용어 정의

본 문서에서 사용할 용어의 혼동을 막기 위해 정의함.

• 인덱스(index), 인덱스 값 : 배열에서 요소의 위치값. 코드 arr[0] 에서 0에 해당하는 값
• 실제 값, 요소(element) : 배열의 특정 위치에 저장된 실제 값. 코드 [1,2,3,4]에서 print(arr[0])을 하면 나오는 값

선택 정렬(Selection Sort)

가장 작은 요소를 선택해서 앞으로 보냄.

크기가 10인 배열이면

• 0~9 중 가장 작은 요소 n1를 배열의 index 0으로 보내고 index 0에 있던 요소를 n1가 있던 위치로 보냄
• 1~9 중 가장 작은 요소 n2를 배열의 index 1으로 보내고 index 1에 있던 요소를 n2가 있던 위치로 보냄

위 과정을 반복하면 작은 순서데로 배열의 인덱스 0, 1, 2 ... 에 차례로 보내면서 정렬이 됨.

배열의 크기가 10일 때, 첫 번째 시도에서 10개, 두 번째 시도에서 9개, 세 번째 시도에서 8개... 총

10 + 9 + 8 ... 1 까지 등차수열을 이루므로 검사 횟수는 n+(n+1)/2 시간 복잡도는 O(n^2)

public static void main(String[] args) {
  System.out.println(Arrays.toString(sort(new int[]{10, 5, 1, 3, 6, 4})));
}
public static int[] sort(int[] arr) {
  for (int i=0; i<arr.length; i++) {
    int min = Integer.MAX_VALUE;
    int lastMinIndex = 0;
    for (int j = i; j < arr.length; j++) {
      if (arr[j] < min) {
        min = arr[j];
        lastMinIndex = j;
      }
    }
    int temp = arr[i];
    arr[i] = arr[lastMinIndex];
    arr[lastMinIndex] = temp;
    System.out.println("i : " + i + ", " + Arrays.toString(arr));
  }
  return arr;
}

// System.out.println
i : 0, [1, 5, 10, 3, 6, 4]
i : 1, [1, 3, 10, 5, 6, 4]
i : 2, [1, 3, 4, 5, 6, 10]
i : 3, [1, 3, 4, 5, 6, 10]
i : 4, [1, 3, 4, 5, 6, 10]
i : 5, [1, 3, 4, 5, 6, 10]
[1, 3, 4, 5, 6, 10]

버블 정렬(Bubble Sort)

두 개의 수를 비교해가며 큰 요소를 배열의 뒤쪽으로 민다.

• n과 n+1을 비교해서 n이 n+1보다 클 경우 n과 n+1의 자리를 바꾼다.
• n+1과 n+2를 비교해서 n+1이 n+2보다 클 경우 n+1과 n+2의 자리를 바꾼다.

이렇게 반복하다보면 큰 수가 뒤로 밀리고 작은수가 앞으로 온다.

배열의 크기가 n일 때 검사하는 갯수는 첫 번째 try에서 n개, 두 번째 try에서 맨 마지막을 제외한 나머지 검사 갯수 n-1개.. 로 진행하여

선택 정렬과 동일하게 시간 복잡도는 O(n^2)이다.

public static void main(String[] args) {
  System.out.println(Arrays.toString(sort(new int[]{10, 5, 1, 3, 6, 4})));
}
public static int[] sort(int[] arr) {
  for (int i=0; i<arr.length; i++) {
    for (int j=0; j<arr.length-1-i; j++) {
      if (arr[j] > arr[j+1]) {
        int temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
      System.out.println("i/j:" + i + "/" + j + ", " + Arrays.toString(arr));
    }
  }
  return arr;
}

// System.out.println
i/j:0/0, [5, 10, 1, 3, 6, 4]
i/j:0/1, [5, 1, 10, 3, 6, 4]
i/j:0/2, [5, 1, 3, 10, 6, 4]
i/j:0/3, [5, 1, 3, 6, 10, 4]
i/j:0/4, [5, 1, 3, 6, 4, 10]
i/j:1/0, [1, 5, 3, 6, 4, 10]
i/j:1/1, [1, 3, 5, 6, 4, 10]
i/j:1/2, [1, 3, 5, 6, 4, 10]
i/j:1/3, [1, 3, 5, 4, 6, 10]
i/j:2/0, [1, 3, 5, 4, 6, 10]
i/j:2/1, [1, 3, 5, 4, 6, 10]
i/j:2/2, [1, 3, 4, 5, 6, 10]
i/j:3/0, [1, 3, 4, 5, 6, 10]
i/j:3/1, [1, 3, 4, 5, 6, 10]
i/j:4/0, [1, 3, 4, 5, 6, 10]
[1, 3, 4, 5, 6, 10]

삽입 정렬(Insertion Sort)

배열의 두번째 요소를 '선택'하고 이 요소부터 시작해서 그 전 요소가 선택한 요소보다 클 경우 인덱스를 하나 증가시키며

선택한 요소보다 작거나 같은 값을 만나면 만난 값의 위치값 + 1에 선택한 요소의 값을 넣는다.

아래의 경우

1. 인덱스 1(n)인 5를 선택
   1. 인덱스 0(n-1)인 10이 선택했던 값 5보다 크므로 10을 index 0에서 위치값이 하나 증가한 index 1에 넣는다.
      => [10, 10, 1, 3, 6, 4]
   2. 더 이상 비교 진행할 값이 없으므로 마지막으로 검사했던 값의 위치index 0에 선택했던 값5를 넣는다.
      => [5, 10, 1, 3, 6, 4]
2. index 2(n)인 1을 선택
   1. index 1(n-1)인 10이 선택했던 값 1보다 크므로 10를 index 1에서 위치값이 하나 증가한 index 2에 넣는다.
      => [5, 10, 10, 3, 6, 4]
   2. index 0(n-2)인 5가 선택했던 값 1보다 크므로 index 1에 5를 넣는다.
      => [5, 5, 10, 3, 6, 4]
   3. 더 이상 비교 진행할 값이 없으므로 마지막 검사했던 값의 위치 index 0에 선택했던 값 1을 넣는다.
      => [1, 5, 10, 3, 6, 4]
3. index 3(n)인 3을 선택
   1. index 2(n-1)인 10이 선택했던 값 3보다 크므로 10을 index 2에서 위치값이 하나 증가한 index 3에 넣는다.
      => [1, 5, 10, 10, 6, 4]
   2. index 1(n-2)인 5가 선택했던 값 3보다 크므로 5를 index 1에서 위치값이 하나 증가한 index 2에 넣는다
      => [1, 5, 5, 10, 6, 4]
   3. index 0(n-3)인 1이 선택했던 값 3보다 작으므로 위치값이 하나 증가한 index 1에 선택한 값을 넣는다.

위와 같은 과정을 반복한다...

아래 예제의 경우 엘리먼트의 이동을 보기위해 null을 대입하였다.

시간복잡도의 경우 이미 정렬이 되어 있을 경우 첫번째 if문을 두번째 for문의 조건식으로 넣게된다면 하나의 `for`문만 사용하게 되므로 `O(n)`의 시간복잡도를 보이며, 일반적인 경우 `O(n^2)`이라고 볼 수 있다.

public static void main(String[] args) {
  System.out.println(Arrays.toString(sort(new Integer[]{10, 5, 1, 3, 6, 4})));
}
public static Integer[] sort(Integer[] arr) {
  for (int i=1; i<arr.length; i++) {
    int picNum = arr[i];
    System.out.println("pic num : " + picNum + ", start : " + Arrays.toString(arr));
    int j = 0;
    for (j=i-1; j>=0; j--) {
      if (arr[j] < picNum) {
        System.out.println(
          String.format("i:%d, j:%d, no switch : %s", i, j, Arrays.toString(arr)));
        break;
      }
      arr[j+1] = arr[j];
      arr[j] = null;
      System.out.println(
        String.format("i:%d, j:%d, switch : %s", i, j, Arrays.toString(arr)));
    }
    arr[j+1] = picNum;
  }
  return arr;
}

// System.out.println
pic num : 5, start : [10, 5, 1, 3, 6, 4]
i:1, j:0, switch : [null, 10, 1, 3, 6, 4]
pic num : 1, start : [5, 10, 1, 3, 6, 4]
i:2, j:1, switch : [5, null, 10, 3, 6, 4]
i:2, j:0, switch : [null, 5, 10, 3, 6, 4]
pic num : 3, start : [1, 5, 10, 3, 6, 4]
i:3, j:2, switch : [1, 5, null, 10, 6, 4]
i:3, j:1, switch : [1, null, 5, 10, 6, 4]
i:3, j:0, no switch : [1, null, 5, 10, 6, 4]
pic num : 6, start : [1, 3, 5, 10, 6, 4]
i:4, j:3, switch : [1, 3, 5, null, 10, 4]
i:4, j:2, no switch : [1, 3, 5, null, 10, 4]
pic num : 4, start : [1, 3, 5, 6, 10, 4]
i:5, j:4, switch : [1, 3, 5, 6, null, 10]
i:5, j:3, switch : [1, 3, 5, null, 6, 10]
i:5, j:2, switch : [1, 3, null, 5, 6, 10]
i:5, j:1, no switch : [1, 3, null, 5, 6, 10]
[1, 3, 4, 5, 6, 10]

퀵 정렬(Quick Sort)

정렬하고자 하는 숫자 중 하나를 기준으로 두고 기준보다 작은 갚을 왼쪽, 큰 값을 오른쪽에 두면서 정렬하는 방식.

대부분의 경우 정렬하고자 하는 배열의 첫 번째 숫자를 기준으로 두고 이 기준 값을 pivot이라고 부른다.

pivot값의 다음 값을 시작으로 인덱스를 하나씩 증가시키면서 인덱스가 가르키는 실제 값(정렬하고자 하는 요소)이 pivot값 보다 큰 값을 만나면 그 인덱스 값을 x로 두고, 다시 배열의 맨 끝부터 인덱스를 하나씩 감소하면서 pivot값보다 작은 값을 찾아서 그 값을 y로 둔다.

인덱스 y를 하나씩 감소시키면서 이동하다보면 두 가지 경우가 발생할 수 있는데, 인덱스 y의 값(요소의 값이 아님)이 인덱스 x의 값보다 작아진 경우(x를 뛰어넘는 경우, cross라고 표현), 큰 경우가 발생할 수 있다.

인덱스 y값이 인덱스 y보다 값이 작아지면, y의 진행을 멈추고

이렇게 도출된 인덱스 값(실제 값 아님) y가 x보다 작은 경우, x를 넘어간 경우(cross라고 표현)