삽입정렬

해당 포스트의 내용은 리트코드를 공부하며 작성한 내용입니다.

참고

정렬 소개

정렬의 근본적인 문제는 아이템의 콜렉션들에 대한 순서에 대한 것이다.
항목들을 주문하는 방법은 전적으로 비교방법에 따라 다르다. 서재에 있는 책무더기를 분류하는 작업을 하는 경우 작성자의 성을 기준으로 구성할 수 있다. 그러나 책을 빨리 운반해야하는 경우 처음에는 책의 크기에 따라 정리하는 것이 합리적일 수 있다. 이 두가지 문제 모두 정렬에 대한 문제이지만, 중요한것은 문제를 분류하는것에 있어서 비교방법과 관련이 있다는 것이다.
즉, 비교방법이 달라지면 결과가 달라질 수 있다는 것이다. 가장 기본적인 수준에서의 정렬 알고리즘은 해당 요소의 공통 특성을 기반으로 컬렉션의 요소를 재구성하는 것이다.

정렬관계는 두가지 주요 속성을 가지고있다.

첫번째로 두 요소 a,b가 주어졌을 때 다음의 것들은 만드시 참이다.

a < b
a = b or a > b (삼분법의 법칙)

두번째,

a < b and b < c then a < c (전이성의 법칙)

정렬은 순서 관계에 따라 모든 요소를 내림차순으로 정렬하는 요소 시퀀스의 재배열로 공식적으로 정의된다.

문자열 목록이 주어졌다고 가정해보면,

[“hello”, “world”, “we”, “are”, “learning, “sorting”]

여기에서 정렬하는 방법으로 하나는 문자열의 길이를 기준으로 하는 것이다. 이 기준을 토대로 정렬 하면

[“we”, “are”, “hello”, “world”, “sorting”, “learning”]}[“we”, “are”, “hello”, “world”, “sorting”, “learning”]

목록에 나열된 각각의 인접요소의 쌍은 선행 문자열의 길이는 다음 문자열의 길이보다 항상 작거나 같다.

또 다른 기준으로는 문자열의 모음 수가 있다. 그렇게 되면 다음과 같은 순서를 보인다.

[“we”, “world”, “are”, “hello”, “sorting”, “learning”]

정렬은 프로그래밍 언어에서 비교방법으로 정의된다. 대부분의 프로그래밍 언어에서는 요소들의 시퀀스를 정렬할 때마다 비교를 위해 사용자 정의 함수를 사용할 수 있습니다.

import java.util.Arrays;

public class Solution {
    public void sortByLength(String[] arr) {
        // Sorts a list of string by length of each string
        Arrays.sort(array, new StringCompare());
    }
}

public class StringCompare implements Comparator<String> {
    public int compare(String s1, String s2) {
        if (s1.length() > s2.length()) {
        //길이를 비교하는 부분
            return 1;
        } else if (s1.length() < s2.length()) {
            return -1;
        }
        return 0;
    }
}

정렬에서 중요한 개념은 inversions(반전) 이다. 시퀀스의 반전은 순서관계에 대해 순서가 맞지 않는 요소 쌍으로 정의된다. 이 말을 더 잘 이해하기 위해 순서 관계가 문자열의 길이로 정의된 이전 문자열 예제를 살펴보자.

[“are”, “we”, “sorting”, “hello”, “world”, “learning”]

분명 위의 목록은 문자열의 길이에 따라 정렬되지는 않았다. 하지만 얼마나 비정렬 인지에 대해 메트릭을 정의 해야 한다면 어떻게 될까? 반전(크기가 큰 원소가 크기가 작은 원소보가 앞에 있는 경우)은 이를 정의하는 방법을 제공한다.

위의 정렬되지 않은 목록에는 다음과 같은 반전이 있다.

(“are”, “we”), (“sorting”, “hello”) , and (“sorting”, “world”)

역전이 많을수록 목록이 더 비순차적이다. 이런 반전의 개념은 정렬의 대체 정의를 소개한다.
즉, 반전을 통해 정렬의 목표를 보여줄 수 있다는 뜻이다.
고로 정렬의 정의는 다음과 같다. n개의 반전이 있는 요소 시퀀스가 주어지면 정렬 알고리즘은 반전을 0으로 줄이는 일련의 작업 이다.

다음으로 언급할 정렬의 중요한 개념은 정렬 알고리즘의 안정성 이다.
안정적인 정렬 알고리즘의 핵심 기능은 동일한 요소의 순서를 유지한다는 것이다.

(원본) [“hello”, “world”, “we”, “are”, “learning, “sorting”]

문자열 길이라는 비교 기준이 있는 이전 문자열 예제에서는 두가지 경우의 시퀀스가 유효하다.

(1) [“we”, “are”, “hello”, “world”, “sorting”, “learning”]

(2) [“we”, “are”, “world”, “hello”, “sorting”, “learning”]

동일한 요소인 'hello' 와 'world'가 원래 시퀀스와 상대적으로 동일한 순서로 유지되기 때문에 (1)을 안정적인 정렬로 간주한다.

퀴즈

['hello', 'your', 'above', 'year', 'alone', 'friendly', 'crazy']

길이를 순서로 정렬한다고 가정하였을 때 가장 안정적인 정렬은 무엇인가 ?

정답 : ['your', 'year', 'hello', 'above', 'alone', 'crazy', 'friendly']

4글자인 your,year 두개의 단어를 제외한 배열의 원래 순서가 보존되어 있다.

[3, 4, 6, 5, 2] 해당 정수배열에 몇개의 반전이 존재하는가 ?

정답 : 5개

3 > 2 , 4 > 2 , 6 > 2 , 5 > 2 6 > 5

다음 중 정렬관계에 있어서 핵심적인 부분은 무엇인가 ?

정답

If a < b and b < c, it must be true that a < c (전이성의 법칙)

It must be true that a < b or a = b or a > b (삼분법의 법칙)

비교 기반 정렬

비교기반정렬은 순서 지정 관계에 의해 정의된 직접적인 비교 방법이 필요한 정렬 알고리즘이다.
어떤 의미에서는 직관적으로 요소 정렬에 대해 생각해볼때 본능적으로 서로 비교하는 것에 대해 생각하기 때문에 가장 자연스러운 정렬 알고리즘이다. 다음 챕터에서는 기본적인 비교 기반 정렬 알고리즘 중 일부에 대해 공부할 것이다.

선택정렬

가장 무거운 책이 맨 아래에 있고 가장 가벼운 책이 맨 위에 오도록 책 더미를 무게에 따라 분류해야한다고 가정해보자. 합리적인 분류 방법 중 하나는 책을 뒤져서 가장 무거운 책을 찾은 다음 맨 아래에 놓는 것이다.
그런 다음 남은 책 더미에서 다음으로 가장 무거운 책을 찾아 가장 무거운 책 위에 놓을 수 있다. 정렬 된 책 더미가 생길 때까지 이 방법을 계속한다. 이 개념이 바로 선택정렬이다.

모든 요소가 정수인 요소 컬렉션이 있다고 가정해보자. 선택 정렬은 해당 목록에서 최소 요소를 반복적으로 찾고 교체를 통해 목록 맨 앞으로 이동하여 정렬된 목록을 작성한다. 전체 목록이 정렬될 때까지 요소를 적절하게 교환한다.

단순성 측면에서 보면 매우 직관적인 알고리즘이며, 작성하기가 그리 어렵지 않다. 불행히도 매우 느리고, 정렬을 하기위해서 O(n^2) 의 시간이 필요하므로, 가장 최악의 케이스라고 볼 수있다.
더불어 최소요소를 찾기 위해 전체 배열을 검색해야 한다. 이 의미는 즉,전체 배열을 뒤지는데 n+(n−1)+(n−2)+…+1 계산을 해야한다는 소리이며 이것은 O(n^2) 을 의미한다.
공간 복잡도는 O(1)이다. 이는 알고리즘 중에 추가 공간을 사용하지 않기 때문이다. 모든 작동은 제 자리에서 이루어진다 !

이것은 안정적인 정렬 알고리즘이라고 볼 수 없다. 예를 들어 다음과 같은 배열이 있다고 가정해보자.

[4, 2, 3, 4, 1]

첫번째 선택정렬 순회 이후에 우리는 [1, 2, 3, 4, 4] 와 같은 배열을 얻을 수 있다.
이 배열은 정렬된것이다. 그러나 동일한 요소에 대한 순서를 보장하지는 못한다.

구현해보기

def solution(arr) :
    answer = []

    for i in range(0,len(arr)):
        min_index = i
        for j in range(i+1,len(arr)):
            if arr[j] < arr[min_index] :
                min_index = j
            #다 비교한 후 가장 작은 애가 min_index에 남음


        arr[i],arr[min_index] = arr[min_index],arr[i]
        print(arr)
        
        #python swap문법

    return answer

if __name__ == '__main__':
    input1 = [7,3,2,5,6,10,9,8,1]
    answer1 = solution(input1)

    print(answer1)

<출력화면>

-> 선택정렬의 단점이 보이는 결과화면,비교할 필요가 없는 경우에도 계속해서 비교를 해야한다.

문제 풀어보기

빨간색,흰색,파란색상의 객체가 있는 배열 nums가 주어지면 동일한 색상의 객체가 인접하도록 해당 위치에서 정렬하며, 색상의 순서는 빨간색 - 흰색 - 파란색 이다.

빨간색 - 0
흰색 - 1
파란색 - 2

<풀이>

기준 : 같은 색상의 객체가 근처에 있도록 해야하며, 0,1,2 순서를 유지해야한다.

가장 첫번째 기준은 0 > 1 > 2 의 순서를 유지하는 것이고 여기에 중복되는 객체가 있다면 중복되는 것끼리 모여있어야 한다.

def solution(nums):

    for i in range(len(nums)):
        min_index = i
        for j in range(i+1,len(nums)):
            if nums[j] < nums[min_index] :
                min_index = j
        nums[i],nums[min_index] = nums[min_index],nums[i]

    return nums

if __name__ == '__main__':
    input1 = [2,0,2,1,1,0]
    input2 = [2,0,1]

    answer1 = solution(input1)
    answer2 = solution(input2)

    print(answer1,answer2)

추가적인 참고 솔루션

링크

해당 문제는 삽입정렬를 위한 문제같지는 않고 네덜란드 국기 문제라고는 하는데, 현재 공부하고 있는 것과는 관련성이 떨어진다고 생각하여 참고 링크만 걸어둔다. 추후 들어가서 볼 예정.

정리

정렬은 요소의 공통 특성을 기반으로 컬렉션의 요소를 재구성한다고 볼 수 있다.

정렬은 두가지 주요 속성을 가지고 있다.

첫번째 삼분법의 원칙,

a < b
a = b or a > b

두번째 전이성의 법칙,

a < b and b < c then a < c

정렬의 반전은 정렬을 설명하는데에 아주 중요한 개념이다. 반전이란 순서관계에 대해 순서가 맞지 않는 요소 쌍이다.

반전이 많을수록 리스트가 비순차적이다.

즉, n개의 반전이 있는 요소 시퀀스가 주어지면 정렬 알고리즘은 반전을 0으로 줄이는 일련의 작업이다.

안정적인 정렬 알고리즘의 핵심 기능은 동일한 요소의 순서를 유지한다는 것이다. 이는, 정렬 이전의 시퀀스를 어느정도 유지하고 있는 알고리즘을 더 안정적이라고 말하는 것과 같다.

선택정렬

• 선택된 원소와 선택된 원소 이후의 원소를 비교한다. 선택된 원소와 비교했을 때 작다면 min_index에 들어있는 값보다 작다면 해당 값의 index를 min_index에 넣는다
• 가장 비효율적인 정렬 방법.
• O(n^2)의 시간 복잡도를 가지고 있다
• O(1)의 공간 복잡도를 가지고 있다 > 별다른 공간사용이 필요하지 않고 주어진 배열에서 swap을 진행한다.