게시 됨 업데이트 됨Dev9분안에 읽기 (약 1393 단어)

sort

정렬 알고리즘

컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 흔히 유용하게 쓰인다. 이 알고리즘의 결과는 반드시 다음 두 조건을 만족해야 한다.

  1. 출력은 비 내림차순(각각의 원소가 전 순서 원소에 비해 이전의 원소보다 작지 않은 순서)이다.
  2. 출력은 입력을 재배열하여 만든 순열이다.

분류

  • 원소들의 크기 비교에 따른 계산 복잡도. 직렬 정렬 알고리즘의 경우 최선 동작은 O(n log n), 최선 동작 중 병렬 정렬은 O((log n)^2), 최악 동작은 O(n^2)이다.
  • 일반적인 방식 : 삽입, 교환, 선택, 병합 등. 교환 정렬에는 거품 정렬과 퀵 정렬이 있다. 선택 정렬에는 셰이커 정렬과 힙 정렬이 있다.

비교 정렬

비교 정렬은 O(n log n)보다 더 나은 성능을 낼 수 없다.

  1. 삽입 정렬 : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 시간 복잡도는 O(n^2)이다.
1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){
      int temp = arr[index];
      int aux = index - 1;
      while( (aux >= 0) && ( arr[aux] > temp ) ) {
         arr[aux+1] = arr[aux];
         aux--;
      }
      arr[aux + 1] = temp;
   }
}
  1. 교환 정렬 (버블 정렬) : 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
void bubbleSort(int[] arr) {
    int temp = 0;
    for(int i = 0; i < arr.length; i++) {
        for(int j= 1 ; j < arr.length-i; j++) {
            if(arr[j]<arr[j-1]) {
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

  1. 선택 정렬(Selection Sort) : 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

    • 주어진 리스트 중에 최솟값을 찾는다.
    • 그 값을 맨 앞에 위치한 값과 교체한다.
    • 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      void selectionSort(int[] list) {
          int indexMin, temp;

          for (int i = 0; i < list.length - 1; i++) {
              indexMin = i;
              for (int j = i + 1; j < list.length; j++) {
                  if (list[j] < list[indexMin]) {
                      indexMin = j;
                  }
              }
              temp = list[indexMin];
              list[indexMin] = list[i];
              list[i] = temp;
          }
      }

  2. 병합 정렬 (Merge Sort) : O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.

    • 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다.(한 원소만 든 리스트는 정렬된 것과 같으므로)
    • 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 마지막 남은 부분리스트가 정렬된 리스트이다.
    1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
    2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
    3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
    4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
    5. 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// array A[] has the items to sort; array B[] is a work array
void BottomUpMergeSort(A[], B[], n)
{
    for (width = 1; width < n; width = 2 * width)
    {
        for (i = 0; i < n; i = i + 2 * width)
        {
            // Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
            // or copy A[i:n-1] to B[] ( if(i+width >= n) )
            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
        CopyArray(B, A, n);
    }
}

//  Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1  ].
void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
{
    i = iLeft, j = iRight;
    // While there are elements in the left or right runs...
    for (k = iLeft; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
            B[k] = A[i];
            i = i + 1;
        } else {
            B[k] = A[j];
            j = j + 1;
        }
    }
}

void CopyArray(B[], A[], n)
{
    for(i = 0; i < n; i++)
        A[i] = B[i];
}
  1. 퀵 정렬(quick sort) : 분할 정복 방법을 통해 리스트를 정렬한다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.
    • 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
    • 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
    • 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

참조“위키백과”

1. K번째 수

  • 문제 설명
    배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.

예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
2에서 나온 배열의 3번째 숫자는 5입니다.
배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

  • 제한사항
    array의 길이는 1 이상 100 이하입니다.
    array의 각 원소는 1 이상 100 이하입니다.
    commands의 길이는 1 이상 50 이하입니다.
    commands의 각 원소는 길이가 3입니다.
  • 입출력 예
    array commands return
    [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3]
    입출력 예 설명
    [1, 5, 2, 6, 3, 7, 4]를 2번째부터 5번째까지 자른 후 정렬합니다. [2, 3, 5, 6]의 세 번째 숫자는 5입니다.
    [1, 5, 2, 6, 3, 7, 4]를 4번째부터 4번째까지 자른 후 정렬합니다. [6]의 첫 번째 숫자는 6입니다.
    [1, 5, 2, 6, 3, 7, 4]를 1번째부터 7번째까지 자릅니다. [1, 2, 3, 4, 5, 6, 7]의 세 번째 숫자는 3입니다. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int [commands.length];
        int[] temp = {};
        int cnt=0;
        for(int [] command : commands){
            temp = Arrays.copyOfRange(array, command[0]-1, command[1]);
            Arrays.sort(temp);
            answer[cnt++] = temp[command[2]-1];
        }
        
        return answer;
    }
}
  • 후기 : 풀고보니 이전에도 한번 풀었던 문제였다. 어떻게 똑같은 메소드를 사용해서 푼걸 보면 신기하다.

2. 가장 큰 수

3. H-Index

팔로우

링크

업데이트 소식 받기

카테고리

최근 글

아카이브

태그

Java1
정렬1
프로그래머스1
×