Sorting: selection and insertion sort

English

Putting an array in order

Sorting means putting the values of an array in order, usually from small to large.
On the AP CSA exam you must be able to write and trace two sorts: selection sort and insertion sort.
You also need to trace (but not write) a third sort: merge sort. We look at all three here.

한국어

배열을 순서대로 만들기

정렬은 배열의 값을 순서대로 배치하는 것으로, 보통 작은 수에서 큰 수 순입니다.
AP CSA 시험에서는 선택 정렬과 삽입 정렬 두 가지 정렬법을 작성하고 추적할 수 있어야 합니다.
또한 세 번째 정렬인 병합 정렬을 추적해야 하지만 작성할 필요는 없습니다. 여기서는 세 가지를 모두 살펴봅니다.

English

Selection sort: the idea

Walk through the array from left to right.
At each spot i, find the smallest value in the part that is still unsorted (from i to the end).
Swap that smallest value into spot i. Now 0..i is sorted.
Repeat until the whole array is in order.

한국어

선택 정렬: 개념

왼쪽에서 오른쪽으로 배열을 순회합니다.
각 위치 i에서 아직 정렬되지 않은 부분(i부터 끝까지)에서 가장 작은 값을 찾습니다.
그 가장 작은 값을 위치 i로 교체합니다. 이제 0..i은 정렬되었습니다.
전체 배열이 순서대로 될 때까지 반복합니다.

public class Sorter {
    public static void selectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;                       // index of smallest so far
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;                   // found a smaller value
                }
            }
            int temp = a[min];                 // swap a[i] and a[min]
            a[min] = a[i];
            a[i] = temp;
        }
    }
}

English

Selection sort: a trace

Let us sort {5, 2, 4, 1, 3}. The bold part is already sorted.
Each pass picks the smallest value from the rest and swaps it to the front.

한국어

선택 정렬: 추적 예시

{5, 2, 4, 1, 3}를 정렬해 봅시다. 굵게 표시된 부분은 이미 정렬되었습니다.
각 pass마다 남은 부분에서 가장 작은 값을 찾아 맨 앞으로Swap합니다.

start:        [5, 2, 4, 1, 3]
i=0  smallest=1 → swap a[0],a[3]:   [1 | 2, 4, 5, 3]
i=1  smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2  smallest=3 → swap a[2],a[4]:   [1, 2, 3 | 5, 4]
i=3  smallest=4 → swap a[3],a[4]:   [1, 2, 3, 4 | 5]
done:         [1, 2, 3, 4, 5]

English

Insertion sort: the idea

Think of holding playing cards and adding one card at a time into the right place.
Start at index 1. Call this value the key.
Slide bigger values on the left one step to the right, until the key fits.
Drop the key into the gap. Now everything to the left is sorted.

한국어

삽입 정렬: 개념

패카드를 손에 들고 한 장씩 올바른 자리에 넣어보는 것을 생각하세요.
인덱스 1에서 시작합니다. 이 값을 **키(key)**라고 부릅니다.
키가 들어갈 때까지 왼쪽의 큰 값들을 한 칸씩 오른쪽으로 밀어냅니다.
키를 빈 공간에 넣습니다. 이제 왼쪽의 모든 것이 정렬되었습니다.

public class Sorter {
    public static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];                    // the value to place
            int j = i - 1;
            while (j >= 0 && a[j] > key) {     // shift bigger values right
                a[j + 1] = a[j];
                j = j - 1;
            }
            a[j + 1] = key;                    // drop key into the gap
        }
    }
}

English

Insertion sort: a trace

Sort {5, 2, 4, 1, 3} again. The bold part stays sorted as we go.
The key is the value we are inserting on each pass.

한국어

삽입 정렬: 추적 예시

다시 {5, 2, 4, 1, 3}를 정렬합니다. 굵게 표시된 부분은 진행함에 따라 계속 정렬된 상태를 유지합니다.
각 pass마다 key는 우리가 삽입하려는 값입니다.

start:           [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2:  [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4:  [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3:   [1, 2, 3, 4, 5]
done:            [1, 2, 3, 4, 5]

English

Merge sort: trace only

Merge sort uses recursion (lesson 15). You do not write it on the exam, but you must trace it.
Split the array in half again and again, until each piece has one value.
Merge pairs of pieces back together, always keeping them in order.

한국어

병합 정렬: 추적 예시 only

병합 정렬은 재귀(lesson 15)를 사용합니다. 시험에서는 작성하지 않으나 반드시 추적해야 합니다.
배열을 반으로 나누고, 다시 반으로 나누며, 각 조각에 하나의 값만 남을 때까지 반복합니다.
조각 쌍을 다시 합치는데, 항상 순서를 유지하도록 합칩니다.

English

Merge sort: a trace

One value is already "sorted". Merging two sorted pieces gives a bigger sorted piece.

Selection and insertion sort are slow on big arrays (they do about n² steps).
Merge sort is faster on big arrays (about n·log n steps). That is why it matters.

한국어

병합 정렬: 추적 예시

하나의 값은 이미 "정렬"된 상태입니다. 두 정렬된 조각을 합치면 더 큰 정렬된 조각이 됩니다.

split:   [5, 2, 4, 1]
         [5, 2]      [4, 1]
         [5] [2]     [4] [1]
merge:   [2, 5]      [1, 4]
merge:   [1, 2, 4, 5]

선택 정렬과 삽입 정렬은 큰 배열에서 느립니다(약 n²단계).
병합 정렬은 큰 배열에서 빠릅니다(약 n·log n 단계). 이것이 중요한 이유입니다.

English

Common mistakes

Selection and insertion sort are both O(n²).
Trace a small array by hand to check your sort.

한국어

흔한 실수

선택 정렬과 삽입 정렬은 모두 O(n²)입니다.
정렬이 올바른지 확인하기 위해 작은 배열을 손으로 추적해 보십시오.

English

Now you try

Each task gives you a method skeleton with a TODO. Sort the array in place (change a itself).
A hidden Harness sorts several arrays and checks the result.
Press Run to compile, then Check answer.

한국어

이제 직접 해보기

각 과제는 TODO가 있는 메소드 골격을 제공합니다. 배열을 제자리에서 in-place 정렬하십시오(a 자체를 변경).
숨겨진 Harness가 여러 배열을 정렬하여 결과를 확인합니다.
컴파일하려면 Run을 누르고, 그 후 Check answer를 누르십시오.

Explore · ⁨탐색하기⁩

Selection / insertion sort

Sorting compares and swaps until the list is ordered.

Complete selectionSort(int[] a) so it sorts the array in place from small to large, using selection sort. The checker tests several arrays.

public class Sorter {
    // Sort a from small to large, in place, using selection sort.
    public static void selectionSort(int[] a) {
        // TODO: for each i, find the smallest value from i to the end,
        //       then swap it into position i.
    }
}

Click Run to see the output here. · ⁨출력을 보려면 '실행'을 클릭하세요.⁩

Complete insertionSort(int[] a) so it sorts the array in place from small to large, using insertion sort. The checker tests several arrays.

public class Sorter {
    // Sort a from small to large, in place, using insertion sort.
    public static void insertionSort(int[] a) {
        // TODO: for each i, take a[i] as the key. Shift bigger values on
        //       the left one step right, then drop the key into the gap.
    }
}

Click Run to see the output here. · ⁨출력을 보려면 '실행'을 클릭하세요.⁩

Complete isSorted(int[] a) returning true if the array is in order from small to large (each item is <= the next), else false. An empty or one-item array counts as sorted.

public class Sorter {
    // Return true if a is sorted small to large.
    public static boolean isSorted(int[] a) {
        return false;   // change this
    }
}

Click Run to see the output here. · ⁨출력을 보려면 '실행'을 클릭하세요.⁩

Putting an array in order

배열을 순서대로 만들기

Selection sort: the idea

선택 정렬: 개념

Selection sort: a trace

선택 정렬: 추적 예시

Insertion sort: the idea

삽입 정렬: 개념

Insertion sort: a trace

삽입 정렬: 추적 예시

Merge sort: trace only

병합 정렬: 추적 예시 only

Merge sort: a trace

병합 정렬: 추적 예시

Common mistakes

흔한 실수

Now you try

이제 직접 해보기

Selection / insertion sort

Handout · ⁨교재 자료⁩

Log in or create account · ⁨로그인 또는 계정 만들기⁩

Your subject · ⁨현재 과목⁩

All sections · ⁨모든 섹션⁩

Feedback & help · ⁨피드백 및 도움말⁩