[삼성 전자 PRO] JAVA 정렬 알고리즘

PRO 시험까지 약 3주 정도가 남았는데요.

다시 1일 1잔디 실천해 보겠습니닷 🤪

 

기초 알고리즘 및 자료 구조 기본기 다지기 1탄 !

 

정렬 알고리즘 : 버블 정렬, 선택 정렬, 퀵 정렬, 병합 정렬

 

 

 

버블 정렬 💭

두 인접한 데이터의 크기를 비교해 정렬.

시간 복잡도 O(n²)

public class Main {
  public static int[] array = new int[5];

  public static void main(String[] args) {

    array = new int[] { 5, 3, 1, 7, 9 };

    bubbleSort(array);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
  }

  static void bubbleSort(int[] array) {
    int temp = 0;
    for (int i = 0; i < array.length - 1; i++) {
      for (int j = 1; j < array.length - i; j++) {
        if (array[j] < array[j - 1]) {
          temp = array[j - 1];
          array[j - 1] = array[j];
          array[j] = temp;
        }
      }
    }
  }

}

 

 

 

선택 정렬 💭

데이터에서 최솟(최댓)값을 찾아 선택하고, 선택된 최솟값을 순서대로 바꿔가면서 정렬

시간 복잡도 O(n²)

 

1. 데이터에서 최솟(최댓)값을 찾음.

2. 가장 앞에 있는 데이터와 선택된 데이터 swap

3. 가장 앞에 있는 index + 1

4. 계속 반복.

 

 

public class Main {
  public static int[] array = new int[5];

  public static void main(String[] args) {

    array = new int[] { 5, 3, 1, 7, 9 };

    selectionSort(array);
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
  }

  static void selectionSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
      int minIdx = i;
      for (int j = i + 1; j < array.length; j++) {
        if (array[j] < array[minIdx]) {
          minIdx = j;
        }
      }
      int temp = array[i];
      array[i] = array[minIdx];
      array[minIdx] = temp;
    }

  }

}

 

 

 

퀵 정렬 💭

데이터에서 최솟(최댓)값을 찾아 선택하고, 선택된 최솟값을 순서대로 바꿔가면서 정렬

시간 복잡도 O(n²)

 

 

 

 

병 정렬 💭

데이터에서 최솟(최댓)값을 찾아 선택하고, 선택된 최솟값을 순서대로 바꿔가면서 정렬

시간 복잡도 O(n²)