거품 정렬(Bubble sort) / 선택 정렬(Selection sort) / 삽입 정렬(Insertion sort)

1. 거품정렬(Bubble sort)

인접한 두 원소를 비교해 조건에 따라 자리를 교환(swap)하여 정렬하는 방법.

안정 정렬(stable sort)이며 구현이 간단하고 소스 코드또한 직관적이므로 자주 사용되지만 시간 및 공간복잡도가 모두 O(n²)로 비효율적임.

 

https://resultswebsitedesign.com/bubble-sort-algorithm/

 

Java구현 코드(오름차순)

내림차순 정렬은 조건을 반대로 해주기만 하면 됩니다.

 

static void bubblesort(int []arr) {
    System.out.println("정렬 전 : " + Arrays.toString(arr));

    // 배열 원소를 담아둘 변수
    int temp;
    
    for (int i = 0; i < arr.length; i++) {
      for (int j = 1; j < arr.length-i; j++) {
        // 앞의 원소가 뒤의 원소보다 클 경우 swap
        if(arr[j-1] > arr[j]) {
          temp = arr[j-1];		// 앞의 원소를 temp에 담고
          arr[j-1] = arr[j];		// 앞의 원소에 뒤의 값(더 작은 값)을 담음
          arr[j] = temp;		// 뒤의 값 자리에는 앞의 값(더 큰값)을 담아 swap완료
        }
      }
    }
	System.out.println("정렬 후 : " + Arrays.toString(arr));
}

콘솔 출력 결과

 

2. 선택정렬(Selection sort)

자리를 선택하고, 그 자리에 올 원소를 찾아 정렬(맨 앞부터 정렬).

거품정렬은 1회전 후 최대값이 맨 끝에 가게되고, 선택정렬은 1회전 후 최소값이 맨 앞에 오게됨.

거품정렬과 비슷하지만 비교 횟수가 더 적기 때문에 비교적 효율적임. 거품정렬과 달리 불안정 정렬(unstable sort)임.

1회전시 최소값을 맨 앞에, 2회전 시 두 번째 최소값을 두 번째 자리에...

 

https://gfycat.com/ko/snappymasculineamericancicada

 

Java구현 코드(오름차순)

내림차순 정렬은 조건을 반대로 해주기만 하면 됩니다.

 

static void selectionsort(int []arr) {
    System.out.println("정렬 전 : " + Arrays.toString(arr));
    
    // 선택한 위치, 배열 원소를 담아둘 변수
    int indexMin, temp;
    
    for (int i = 0; i < arr.length-1; i++) {
      indexMin = i;	// 위치 선택
      	for (int j = i + 1; j < arr.length; j++) {
          if(arr[indexMin] > arr[j]) {	// 선택한 위치의 원소가 다음 원소보다 클 경우
          	indexMin = j;		// 선택한 위치값 갱신.. 최소값을 찾는 과정
          }
    	}
    
      // arr[indexMin], arr[i] swap
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
        System.out.println((i+1)+"회전 : " + Arrays.toString(arr));
    }

    System.out.println("정렬 후 : " + Arrays.toString(arr));
}

콘솔 출력 결과

 

 

3. 삽입 정렬(Insertion sort)

선택정렬과 비슷하나 더 효율적인 정렬. 

index 1(두 번째)원소 부터 시작하며 자신보다 앞에 있는 원소들과 비교하여 정렬함.

평균과 최악의 경우 O(n^2)의 시간복잡도를 가지며 최선의 경우(이미 정렬이 많이 되어있는 경우) O(n)의 시간복잡도를 가짐.

제자리 정렬이며 안정 정렬(stable sort)임. 거품정렬이나 선택정렬보다 효율적.

 

https://gfycat.com/ko/densebaggyibis

 

Java구현 코드(오름차순)

내림차순 정렬은 조건을 반대로 해주기만 하면 됩니다.

 

static void insertionSort(int[] arr) {
    System.out.println("정렬 전 : " + Arrays.toString(arr));
    
    // 두 번째 원소부터 시작하므로 index = 1
    for (int index = 1; index < arr.length; index++) {
      int temp = arr[index];		
      int prev = index - 1;

      // 현재 비교하는 원소보다 앞에 있는 모든 원소들과 비교
      while(prev >= 0 && (arr[prev] > temp)) {
        arr[prev + 1] = arr[prev];	// 큰 값을 뒤로 이동
        prev--;
      }
      
      // prev는 현재 비교하는 원소보다 작은 값 중 가장 큰 값의 index이므로 바로 뒤에 현재 원소값을 삽입
      arr[prev + 1] = temp;	
      System.out.println(index +"회전 : " + Arrays.toString(arr));
    }
    System.out.println("정렬 후 : " + Arrays.toString(arr));
}

콘솔 출력 결과