[자바기초.030] Sorting Algorithms

[자바기초.030] Sorting Algorithms

 

• 데이터를 정렬하는 알고리즘은 아주 많습니다.
• 이곳에서 다룰 정렬 알고리즘은 Selection, Insertion, Merge 정렬 알고리즘 입니다.

 

 

1.Selection Sort

• 선택 정렬(selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
  1.주어진 리스트 중에 최소값을 찾는다.
  2.그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
  3.맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
• n개의 주어진 데이터를 이와 같은 방법으로 정렬하는 데에는 Θ(n^2) 만큼의 시간이 걸린다.(이중 for문)
• 좀 더 자세히 설명하면, Selection Sort(선택 정렬)는 첫 번째 데이터를 두 번째 데이터부터 마지막 데이터까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 데이터를 세 번째 데이터부터 마지막 데이터까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
• 1회전을 수행하고 나면 가장 작은 값의 데이터가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 데이터를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 데이터를 정렬한다.

 

https://www.youtube.com/watch?v=Ns4TPTC8whw

 

 

 

[예제1]

아래의 Selection Sort 예제 코드를 실행해 보세요.

import java.util.Arrays;
 
public class SortTest
{
    public static void selectionSort(int[] elements)
    {
        for (int j = 0; j < elements.length - 1; j++)
        {
            int minIndex = j;
            for (int k = j + 1; k < elements.length; k++)
            {
                if (elements[k] < elements[minIndex])
                {
                    minIndex = k;
                }
            }
            int temp = elements[j];
            elements[j] = elements[minIndex];
            elements[minIndex] = temp;
        }
    }
 
    public static void main(String[] args)
    {
        int[] arr1 = {3, 86, -20, 14, 40};
        System.out.println(Arrays.toString(arr1)); // [3, 86, -20, 14, 40]
        selectionSort(arr1);
        System.out.println(Arrays.toString(arr1)); // [-20, 3, 14, 40, 86]
    }
}
 

 

 

[유제1-1]

Under what condition will a selection sort execute faster?

 

A. If the data is already sorted in ascending order
B. If the data is already sorted in descending order
C. It will always take the same amount of time to execute

D. If the data is randomly sorted.

 

 

[유제1-2]

This method should sort the numbers in the passed array into ascending order. But, it does not work. Which of the following lines is wrong?

public static void selectionSort(int[] elements)
{
  for (int j = 0; j < elements.length − 1; j++)      // line 1
  {
     int minIndex = j;                               // line 2
     for (int k = 0; k < elements.length; k++)       // line 3
     {
        if (elements[k] < elements[minIndex])        // line 4
        {
           minIndex = k;                             // line 5
        }
     }
     int temp = elements[j];
     elements[j] = elements[minIndex];
     elements[minIndex] = temp;
   }
}

 

A. line 1
B. line 2
C. line 3
D. line 4
E. line 5

 

 

2.Insertion Sort

• 삽입 정렬(insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
•  이 알고리즘은 O(n^2)의 시간이 걸린다.(이중 반복문)

 

https://youtu.be/ROalU379l3U?si=leApS8NiLHWJu2r0

 

 

[예제2]

아래의 Insertion Sort 예제코드를 실행해 보세요.

import java.util.Arrays;
 
public class SortTest
{
    public static void insertionSort(int[] elements)
    {
        for (int j = 1; j < elements.length; j++)
        {
            int temp = elements[j];
            int possibleIndex = j;
            while (possibleIndex > 0 && temp < elements[possibleIndex - 1])
            {
                elements[possibleIndex] = elements[possibleIndex - 1];
                possibleIndex--;
            }
            elements[possibleIndex] = temp;
        }
    }
 
    public static void main(String[] args)
    {
        int[] arr1 = {3, 86, -20, 14, 40};
        System.out.println(Arrays.toString(arr1)); // [3, 86, -20, 14, 40]
        insertionSort(arr1);
        System.out.println(Arrays.toString(arr1)); // [-20, 3, 14, 40, 86]
    }
}
 

 

[유제2-1]

Under what condition will an insertion sort execute faster?

 

A. If the data is already sorted in ascending order
B. If the data is already sorted in descending order
C. It will always take the same amount of time to execute

 

 

[유제2-2]

This method should sort the numbers in the passed array into ascending order. But, it does not work. Which of the following lines is wrong?

public static void insertionSort(int[] elements)
{
  for (int j = 1; j < elements.length - 1; j++)                       // line 1
  {
     int temp = elements[j];                                          // line 2
     int possibleIndex = j;                                           // line 3
     while (possibleIndex > 0 && temp < elements[possibleIndex - 1])  // line 4
     {
        elements[possibleIndex] = elements[possibleIndex - 1];        // line 5
        possibleIndex--;
     }
     elements[possibleIndex] = temp;
  }
}

 

A. line 1
B. line 2
C. line 3
D. line 4
E. line 5

 

 

3.Merge Sort

• 병합 정렬은 배열을 쪼갠 뒤, 다시 병합시키면서 차근차근 정렬해나가는 방식을 사용한다
• 알고리즘 방식은 아래 그림과 같다.

merge sort from wikipedia

 

 

 

https://youtu.be/XaqR3G_NVoo?si=xsQu70AdBoMypChs

 

 

[예제3]

아래의 merge sort 예제코드를 실행해 보세요.

import java.util.Arrays;
 
public class SortTest
{
    public static void mergeSort(int[] elements)
    {
        int n = elements.length;
        int[] temp = new int[n];
        mergeSortHelper(elements, 0, n - 1, temp);
    }
 
    private static void mergeSortHelper(
        int[] elements, int from, int to, int[] temp)
    {
        if (from < to)
        {
            int middle = (from + to) / 2;
            mergeSortHelper(elements, from, middle, temp);
            mergeSortHelper(elements, middle + 1, to, temp);
            merge(elements, from, middle, to, temp);
        }
    }
 
    private static void merge(
        int[] elements, int from, int mid, int to, int[] temp)
    {
        int i = from;
        int j = mid + 1;
        int k = from;
 
        while (i <= mid && j <= to)
        {
            if (elements[i] < elements[j])
            {
                temp[k] = elements[i];
                i++;
            }
            else
            {
                temp[k] = elements[j];
                j++;
            }
            k++;
        }
 
        while (i <= mid)
        {
            temp[k] = elements[i];
            i++;
            k++;
        }
 
        while (j <= to)
        {
            temp[k] = elements[j];
            j++;
            k++;
        }
 
        for (k = from; k <= to; k++)
        {
            elements[k] = temp[k];
        }
    }
 
    public static void main(String[] args)
    {
        int[] arr1 = {86, 3, 43, 5};
        System.out.println(Arrays.toString(arr1)); // [86, 3, 43, 5]
        mergeSort(arr1);
        System.out.println(Arrays.toString(arr1)); // [3, 5, 43, 86]
    }
}

 

• 3 methods: mergeSort, mergeSortHelper, and merge
• mergeSortHelper is recursive
• Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList.
• runtime이 n*log(n) 이다.

 

[유제3-1]

Under what condition will a merge sort execute faster?

 

A. If the data is already sorted in ascending order
B. If the data is already sorted in descending order
C. It will always take the same amount of time to execute

 

 

[유제3-2]

Which sort should be the fastest most of the time?

 

A. selection sort
B. insertion sort
C. merge sort

 

 

4.Sort Runtimes

Sort Algorithm	실행시간
Insertion Sort	n^2
Selection Sort	n^2
Merge Sort	nlog base 2 of n

 

 

 

---

[유제 정답은 아래 "더보기" 클릭]

[유제1-1 정답]

C

(A selection sort always does the same number of comparisons and always takes the same time to execute regardless of the order of the data.)

 

[유제1-2 정답]

C

(The inner loop should start at the outer loop index + 1.)

 

[유제2-1 정답]

A

(If the data is already sorted in the correct order you don't need to move any values.)

 

[유제2-2 정답]

A

(It should loop through the entire array, so  j < elements.lenth  is right.)

 

[유제3-1 정답]

C

(It will take about the same time regardless of the data.)

 

[유제3-2 정답]

C

(Merge sort is always faster than selection sort and usually faster than insertion sort.)