삽입 정렬 이해: 질문 기반 접근 방식

이 블로그 게시물에서는 삽입 정렬 알고리즘의 기본을 이해하기 위해 질문 기반 접근 방식을 취하겠습니다. 나는 삽입 알고리즘과 내가 곧 배우게 될 다른 알고리즘을 이해하는 더 나은 방법을 찾으려고 노력할 때 이 접근 방식을 생각해 냈습니다. 나는 내가 배우게 될 알고리즘의 전부는 아니더라도 대부분에 적용할 수 있는 전략을 구축하고 싶었습니다. 이런 생각을 하면서 첫 번째 원칙을 생각해야겠다는 확신이 들었습니다

첫 번째 원리 사고에서 영감을 받은 이 접근 방식에는 초기 이해가 모호하든 명확하든 먼저 알고리즘을 파악하려고 노력하는 것이 포함됩니다. 그런 다음 알고리즘을 구성하는 작은 개념이나 메커니즘을 식별합니다. 이러한 메커니즘이나 작은 개념에 대한 질문을 형성함으로써 가능합니다. 우리는 본질적으로 우리가 스스로 형성한 질문을 해결하는 데 중점을 두고 작은 다른 관점에서 알고리즘의 작동을 이해하려고 노력하고 있습니다.

귀하가 작성한 답변은 처음에는 실제 알고리즘에 사용된 구문과 유사할 수도 있고 그렇지 않을 수도 있습니다. 목표는 구문이 가까운지 여부에 관계없이 스스로 질문에 대답하는 것입니다. 명확하게 이해한 후에는 알고리즘의 실제 구현과 유사하게 구문을 사용하도록 답변을 변환하고 병합할 수 있습니다. 이 프로세스를 통해 대체 코드 형식을 탐색하고, 특정 구문이 사용되는 이유를 파악하고, 스스로 더 나은 방식으로 극단적인 경우를 처리할 수 있다고 믿습니다.

저는 이 방법을 통해 각 코드 줄의 이론과 추론을 이해하고 구현 프로세스를 더욱 직관적이고 의미 있게 만들 수 있다고 믿습니다. 다음 질문과 제가 겪은 사고 과정은 삽입 정렬을 더 잘 이해하고 효과적으로 코딩하는 데 도움이 되었습니다.

당신의 질문은 다를 수 있습니다. 그것들은 더 많거나 적거나 완전히 다를 수 있습니다. 어떤 사람들은 이것이 리버스 엔지니어링과 비슷하다고 말할 수도 있지만, 뭐라고 부르든 이 방법을 통해 삽입 정렬 알고리즘을 철저하게 이해할 수 있었습니다. 다른 알고리즘에서도 동일하게 수행되기를 바랍니다. 자, 뛰어들자!

삽입정렬 구현

삽입 정렬을 위해 최종적으로 구현하게 될 코드 형식입니다.

def insertion_sort(values):

    for new_value_index in range(1,len(values)):

        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1

        values[index+1] = new_value

질문

정렬된 목록이 주어지면 while 루프를 사용하여 오른쪽에서 왼쪽으로 값을 인쇄합니다.

values = [4,8,12,16,20,24,30]
# given a sorted list, using while loop, print values from right to left.

index = len(values)-1
while index>=0:
    print(values[index],end = " ")
    index-=1

정렬된 목록과 새 값이 주어지면 목록 정렬을 유지하기 위해 새 값이 삽입될 인덱스를 찾습니다.

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# using while loop, if traversing from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value: break
    index-=1

print(values,new_value,index)

정렬된 목록과 새 값이 주어지면 정렬된 상태를 유지하도록 목록에 새 값을 삽입하세요.

values = [4, 8, 12, 16, 20, 24]
new_value = 14

# if traversal from right to left

index = len(values)-1
while index>=0:
    if values[index]<new_value:break
    index-=1

values = values[:index+1] + [new_value] + values[index+1:]
print(values)

정렬된 목록이 주어지고 새 값이 추가되면 새 값을 지정된 인덱스 위치로 이동합니다.

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

given_index = 3

# above given

n = len(values)-1

index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

print(values)

values[given_index+1] = new_value

print(values)

정렬된 목록이 주어지고 새 값을 추가하여 목록을 정렬합니다.

values = [4, 8, 12, 16, 20, 24, 30]

new_value = 14

values.append(new_value)

print(values)

### given a sorted list, then appended with new value, sort the list
####

n = len(values)-1
new_value = values[-1]

# find the index at which the value is to be inserted
# right to left
index = n-1
while index>=0:
    if values[index]<new_value:break
    index-=1
given_index = index 
print("given_index : "  , given_index)

# move the values forward by one step until we reach the given index
index = n-1
while index>given_index:
    values[index+1] = values[index]
    index-=1

values[index+1] = new_value

print(values)

정렬된 목록이 주어지고 새 값을 추가하여 목록을 정렬합니다.

values = [4, 8, 12, 16, 20, 24, 30]

new_values = [14,32]

values += new_values

print(values)

# given a sorted list, then appended with two new value(s), sort the list

n = len(values)-1

new_value_start_index = n - 1

print(new_value_start_index, values[new_value_start_index])

for new_value_index in range(new_value_start_index,len(values)):

    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value: break
        values[index+1] = values[index]
        index-=1

    values[index+1] = new_value

print(values)

목록이 주어지면 정렬하세요.

import random

values = random.sample(range(10,90), k = 10)

values

print(values)

for new_value_index in range(1,len(values)):
    new_value = values[new_value_index]

    index = new_value_index-1
    while index>=0:
        if values[index]<new_value:break
        values[index+1] = values[index]
        index-=1
    values[index+1] = new_value

print(values)

삽입정렬 구현

def insertion_sort(values):
    for new_value_index in range(1,len(values)):
        new_value = values[new_value_index]

        index = new_value_index-1
        while index>=0:
            if values[index]<new_value:break
            values[index+1] = values[index]
            index-=1
        values[index+1] = new_value

추가 자료

처음에는 알고리즘을 더 잘 이해하기 위해 포괄적인 질문 세트를 진행했지만, 위의 질문은 삽입 정렬을 더 나은 방식으로 이해하는 데 중요하다고 생각하는 질문 세트입니다. 제가 작업한 질문을 모두 포함하면 글이 꽤 길어질 것 같습니다.

모든 질문을 보고 싶은 분들을 위해 내 답변이 포함된 전체 질문 세트가 포함된 Jupyter Notebook을 만들었습니다. 이를 통해 삽입 정렬 구현을 완전히 이해할 수 있었습니다.

더 자세히 알아보고 싶다면 노트북을 확인해 보시기 바랍니다.

수정과 제안을 환영합니다.

위 내용은 삽입 정렬 이해: 질문 기반 접근 방식의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!