[알고리즘] 버블정렬, 삽입정렬, 선택정렬 구현코드

[버블정렬]

/*
1. 버블정렬은 인접한 원소들을 비교하여 정렬을 하는 것으로 현재 원소보다 현재 원소 -1에 위치한 원소의 크기가 클 경우 자리를 교체한다.
2. 교체 방법은 교체할 원소를 저장할 임시 변수 temp를 만들고, temp에 현재 원소를 저장한 후 현재 원소 -1 위치에 현재 원소를 저장하고 현재 원소 위치에 temp변수의 값을 저장하는 방법으로 차례대로 변경한다.
3. 모든 원소를 차례대로 비교하며 정렬을 하는 방법이기 때문에 최악, 최선, 평균의 시간복잡도는 O(n^2)임을 확인할 수 있다.
4. 구현이 간단하고 코드가 직관적이지만, 최선, 최악, 평균의 시간복잡도가 모두 O(n^2)이기 때문에 효율적인 정렬방법은 아니다.
*/
import java.io.*;
import java.util.*;

class Main {  
  public static void main(String args[]) {
    // 버블정렬
    int[] array = {30, 9, 10, 13, 14, 4, 7, 20};
	
    // 임시 숫자를 저장할 변수
    int temp = 0;
    for(int i = 1; i <= array.length; i++) {
      for(int j = 0; j < array.length - i; j++) {
        if(array[j] > array[j + 1]) {
          temp = array[j + 1];
          array[j + 1] = array[j];
          array[j] = temp;
        }
      }
    }

    System.out.println("======정렬결과======");
    for(int item : array) {
      System.out.print(item + " ");
    }
  } 
}

[선택정렬]

/*
1. 선택정렬은 앞에서부터 정렬을 수행합니다. 배열을 탐색하면서 가장 작은 위치의 값을 가진 인덱스를 저장합니다.
2. 작은 위치의 값을 가진 인덱스와 i번째 원소를 변경하며 앞에서부터 차례대로 정렬하는 방법입니다.
3. 시간복잡도는 최선, 최악, 평균 O(n^2)입니다.
*/
import java.io.*;
import java.util.*;

class Main {  
  public static void main(String args[]) {
    // 선택정렬
    int[] array = {30, 9, 10, 13, 14, 4, 7, 20};

    // SelectionSort메소드 호출 및 결과 값 저장
    String result = Arrays.toString(SelectionSort(array));

    // 결과 값 출력
    System.out.println(result);
  }

  public static int[] SelectionSort(int[] array) {
    // 최솟값의 위치를 저장할 변수
    int minIndex = 0;
    for(int i = 0; i < array.length; i++) {
      minIndex = i;
      for(int j = i + 1; j < array.length; j++) {
        if(array[minIndex] > array[j]) {
          minIndex = j;
        }
      }
      
      // Swap과정
      int temp = array[i];
      array[i] = array[minIndex];
      array[minIndex] = temp;
    }
    // 정렬된 배열 리턴
    return array;
  }
}

[삽입정렬]

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

class Main {
    public static void main(String args[]) {
        // 삽입정렬
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2};

        // InsertionSort메소드 호출 및 결과 값 저장
        String result = Arrays.toString(InsertionSort(array));

        // 결과 값 출력
        System.out.println(result);
    }

    public static int[] InsertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
          int j = i;
          while(j > 0 && array[j] < array[j - 1]) {
            int temp = array[j - 1];
            array[j - 1] = array[j];
            array[j] = temp;
            j--;
          }
        }
      // 정렬된 배열 리턴
      return array;
    }
}