[자료구조] 정렬

버블 정렬

백준 2750번

- 첫 번째 for문을 하나의 루프라고 생각해야됨. 첫 번째 루프(i)에서 가장 큰 범위가 뒤로 이동하므로 두 번째 for문에서는 비교 범위에서 제외해야함. 그래서 범위를 N-1-i로 설정함.

- 로직을 생각하긴했는데 하나의 루프를 여러번 반복할 때 가장 큰 범위를 제외시켜야한다는 조건을 생각하지 못했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] array = new int[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            array[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N-1; i++) {
            // 첫 번째 루프(i) 에서 가장 큰 원소가 뒤로 이동하므로 비교 범위에서 제외해야함.
            // 그래서 N-1-i
            for (int j = 0; j < N-1-i; j++) {
                if (array[j] > array[j+1]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            System.out.println(array[i]);
        }
    }
}

---

선택 정렬

백준 1427번

- String 변수로 정렬할 데이터를 받아 int형 배열에 저장해야됨. 이때 substring() 함수를 사용해 숫자를 각 자릿수별로 나눈 후 배열에 저장해야함.

- substring() : 문자열 자르기. 

- 선택 정렬을 할 때 Max 초기값을 지정해주고 옆 배열과 비교해서 최고로 큰 Max값을 찾음.

- 만약 왼쪽이 Max값보다 작으면 두 값을 switch. 

- Max값을 정하는 것부터 switch 시키는 부분이 n. 이 행위를 n번 반복하면 선택 정렬!

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String N = br.readLine();
        int[] array = new int[N.length()];

        for (int i = 0; i < N.length(); i++) {
            array[i] = Integer.parseInt(N.substring(i, i+1));
        }
        for (int i = 0; i < N.length(); i++) {
            int Max = i;
            for (int j = i+1; j < N.length(); j++) {
                if (array[j] > array[Max]) {
                    Max = j;
                }
            }
            if (array[i] < array[Max]) {
                int temp = array[i];
                array[i] = array[Max];
                array[Max] = temp;
            }
        }
        for (int i = 0; i < N.length(); i++) {
            System.out.print(array[i]);
        }

    }
}

---

삽입 정렬

백준 2750번

- 삽입 정렬은 개념은 이해했지만 실제 코드로 구현하는게 너무 어려웠다.....심지어 버블 정렬로 한번 구현해봤던 문제인데, 어려웠다. 꼭 다시 풀어봐야겠다.

- 특히 왜 j--를 해야되는지를 엄청 고민했는데, 그 이유는 오른쪽에서 왼쪽으로 쭉 보면서 선택할 원소를 삽입할 위치를 찾기위해서였다.

- while문 조건이 j >= 0 &&... 인 이유는 j-- 를 계속 해줄 때 -1이 되면 안되니까 붙은 조건이구나 라고 이해했다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] array = new int[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            array[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 1; i < array.length; i++) {
            int temp = array[i]; // 값을 미리 저장
            int j = i-1; // 자기보다 1칸 작은 수부터 비교를 시작함
            while(j >= 0 && array[j] > temp) {
                array[j+1] = array[j];
                j--; // 선택할 원소를 삽입할 위치를 찾기위해 j--
            }
            array[j+1] = temp;
        }
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }

    }
}

---

퀵 정렬

- 퀵 정렬은 문제의 코드를 이해하기가 너무 힘들어서 일단 기본 예제 코드를 공부했다. 일단 알고리즘을 전부 쭉 공부하고 다시 복습하면서 익히려고 한다..

public class QuickSort {

  public static void main(String[] args) {
    int[] arr = { 3, 1, 5, 6, 20, 10, 7, 11, 15, 9 };
    quickSort(arr);
  }

  public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
  }

  private static void quickSort(int[] arr, int start, int end) {
    // start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
    if (start >= end)
      return;
    
    // 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
    int pivot = start;
    int lo = start + 1;
    int hi = end;
    
    // lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
    // 서로 엇갈리게 될 경우 while문 종료
    while (lo <= hi) {
      while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
        lo++;
      while (hi > start && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
        hi--;
      if (lo > hi)				 // 엇갈리면 피벗과 교체
        swap(arr, hi, pivot);
      else
        swap(arr, lo, hi);			 // 엇갈리지 않으면 lo, hi 값 교체 
      }
	
    // 엇갈렸을 경우, 
    // 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
    quickSort(arr, start, hi - 1);
    quickSort(arr, hi + 1, end);

  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

출처: https://erinh.tistory.com/entry/알고리즘-퀵-정렬-Quick-sort-자바-Java 

---

병합 정렬

-> 나중에 문제 추가하기

---

기수 정렬

-> 나중에 문제 추가하기