230616 Today I Learned

정렬 알고리즘의 개념과 정의를 '뇌를 자극하는 알고리즘' 책으로 공부했지만, 이를 코드로 구현해본 적이 없어 블로그에 정리할 겸 오늘부터 순차적으로 구현해보려 한다.

정렬을 해야하는 이유?

정렬 알고리즘 시간복잡도 출처 : Heee's Development Blog

정렬되지 않은 데이터를 탐색하려면 순차 탐색을 수행해야 하는데 모든 데이터를 순환해야 하므로 O(n)이 소요된다.(순차탐색) 하지만 정렬이 되어있으면 이진탐색과 같은 효율적인 검색 알고리즘을 사용할 수 있기 때문에 O(log n)으로 탐색을 할 수 있다.
한마디로, 탐색(검색) 성능을 향상할 수 있기 때문이다.

버블정렬(Bubble Sort)

서로 인접한 두 원소를 검사해 정렬하는 알고리즘

이미지 출처: MLee (개선된 버블 정렬 gif)

• 인접한 2개의 원소를 비교해 크기가 순서대로(기본적으로 오름차순) 되어있지 않으면 서로 교환한다.

• 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하며 회차가 진행되면서 가장 큰 값부터 뒤에서 채워진다.

• 시간복잡도 : (n-1) + (n-2) + (n-3) + .... + 2 + 1 -> n(n-1)/2이므로, 빅 O표기법으로는 O(n^2)이다. 정렬이 되어있건 없건 2 원소를 끝까지 비교하기 때문에 최선, 최악, 평균 모두 시간복잡도가 O(n^2)으로 동일하다.

• 공간복잡도 : 주어진 배열 안에서 교환을 통해 정렬되므로 O(1)이다.

• 장점 : 구현이 간단하고 직관적이며 이해하기가 쉽다.
  다른 공간이 필요하지않는 제자리 정렬이다.
  중복값에 대해 상대적인 순서를 보장하는 안정정렬이다.

• 단점 : 모든 요소를 비교를 통해 swap하기 때문에 비효율적이다.
  시간복잡도가 모든 경우에서 O(n^2)이라 비효율적이라 잘 쓰지 않는다.
  특정 요소가 최종 정렬 위치에 있는 경우라도 교환되는 일이 생긴다.
  불안정 정렬이다.

Java로 버블 정렬 구현

이중 for문으로 밖의 for문은 회차. 안의 for문은 실제 비교와 swap 연산을 하도록 한다. 앞의 값이 뒤의 값보다 크면 swap한다.

  private static void bubbleSort(int [] array){
//    i는 회차를 의미한다. n개가 있으면 n-1회차를 수행하기 때문에 array.length -1을 한다.
    for (int i = 0; i < array.length -1; i++) {
//      j는 j+1값과 비교해 정렬되지 않은 값들을 계속 비교한다.
      for (int j = 0; j < array.length-1-i; j++){
//        오름차순 기준 앞의 값이 뒷값보다 크면 자리를 swap한다.
        if (array[j]>array[j+1]) {
          int tmp = array[j];
          array[j] = array[j+1];
          array[j+1] = tmp;
        }
      }
    }
  }

버블 정렬 개선

한 회차에서 이미 정렬이 다 되어 더이상 swap이 진행되지 않았다면, 이미 정렬이 완료된 것으로 판단해 연산을 줄일 수 있다.

  private static void improvedBubbleSort(int[] array){
    int count = 0;
    boolean isSwapped;
    for (int i = 0; i < array.length -1; i++) {
      isSwapped = false;
      for (int j = 0; j < array.length-1-i; j++){
        count++;
        if (array[j]>array[j+1]) {
          int tmp = array[j];
          array[j] = array[j+1];
          array[j+1] = tmp;
          isSwapped = true;
        }
      }
//      swap된적이 없다면 정렬이 완료된 것으로 판단해 정렬을 종료한다.
      if (!isSwapped) break;
    }
    System.out.println("개선된 버블 정렬에서 연산 횟수 : " + count);
  }

• count는 연산 횟수를 세기 위해 만든 변수라 없어도 된다.

• 개선된 버블정렬은 버블정렬보다는 효율적이라고 할 수 있지만, 여전히 시간복잡도가모든 경우에서 O(n^2)이라 잘 쓰이진 않는다.

최종 출력

• 이미 정렬된 부분은 연산을 skip해 연산 횟수가 줄었다.

public static void main(String[] args) {
    int[] array = {1,2,7,5,4,3,9,6,8,10};
    int[] array2 = Arrays.copyOf(array, array.length);
    System.out.print("정렬 전 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    bubbleSort(array);
    System.out.print("버블정렬 후 배열 : ");
    System.out.println(Arrays.toString(array));
    System.out.println("-----------------------------------------");
    improvedBubbleSort(array2);
    System.out.print("개선된 버블정렬 후 배열 : ");
    System.out.println(Arrays.toString(array2));
  }

소스트리 실행 불가 문제

• 문제 : 소스트리를 실행하면 소스트리 파란 그림만 뜨고 실행이 되지 않았다.

• https://soulduse.tistory.com/37 이 블로그를 참고해 해결

• C:\Users\name\AppData\Local\Atlassian\SourceTree.exe_Url_xx..xx 해당 폴더를 삭제하니 해결되었다.