NOTE 2 배열, 링크 및 정렬 선택

이것 은 의 두 번 째 독서 노트 로 내용 은 주로 배열, 링크 와 선택 정렬 과 관련된다.
1. 배열
1.1 정의
기본 적 인 데이터 구조 로 서 배열 은 n 개의 요소 가 색인 번호 에 따라 메모리 영역 에 순서대로 저장 되 는 데이터 구 조 를 말한다.그 중에서 색인 번호 와 인접 한 요 소 는 메모리 의 위치 에서 도 인접 해 있다.
1.2 장단 점
1.2.1 장점
무 작위 접근 지원.색인 번호 에 따라 대응 하 는 요 소 를 방문 하여 배열 의 요 소 를 빠르게 방문 할 수 있 습 니 다.
1.2.2 단점
(1) 삭제, 삽입 요소 가 느리다.요 소 를 삭제 하거나 삽입 하려 면 요소 뒤의 모든 요 소 를 이동 해 야 합 니 다.(2) 넘 칠 가능성 이 있다.배열 의 메모리 가 부족 하면 전체 배열 을 용량 이 더 큰 메모리 로 옮 겨 야 합 니 다.
1.3 적용 범위
요 소 를 빠르게 접근 해 야 하지만 요 소 를 삽입 하고 삭제 하 는 속도 에 대한 요구 가 높 지 않 은 장면 입 니 다.
2. 링크
2.1 정의
모든 요 소 는 자신의 값 을 기록 하 는 것 외 에 다음 요소 의 메모리 주 소 를 기록 하 는 기본 데이터 구조 입 니 다.
2.2 장단 점
2.2.1 장점
요 소 를 빠르게 삽입 하고 삭제 하 는 것 을 지원 합 니 다.요 소 를 삽입 하고 삭제 하 는 작업 은 간단 합 니 다.특정 요소 가 가리 키 는 메모리 주 소 를 바 꾸 어 삽 입 된 요소 나 삭 제 된 요소 가 가리 키 는 요 소 를 가리 키 도록 합 니 다.
단점
빠 른 접근 요 소 는 지원 되 지 않 습 니 다. 링크 의 첫 번 째 요소 에서 후속 요 소 를 순서대로 방문 하여 목표 요 소 를 찾 아야 합 니 다.
2.3 적용 범위
요 소 를 빠르게 삽입 하고 삭제 해 야 하지만 요 소 를 찾 는 실효 성에 대한 요구 가 낮은 경우 입 니 다.
3. 정렬 방법 선택
3.1 실현 원리
모든 원 소 를 옮 겨 다 니 며 가장 큰 (최소) 원 소 를 찾 아 라.이 를 원래 의 배열 에서 새로운 데이터 구조 로 옮 깁 니 다.그 다음 에 남 은 요소 에서 가장 큰 (최소) 요 소 를 찾 아 상기 이동 요소 의 절 차 를 반복 하고 원래 의 데이터 구조 에서 요소 의 수량 이 0 이 될 때 까지 한다.
3.2 코드 인 스 턴 스

#       
import random

#          
def select_smallest(arr):
    value=float('inf')
    idx=None
    for i in range(0,len(arr)):
        if value>arr[i]:
            value=arr[i]
            idx=i
    return idx


#    
def selection_sort(arr):
    #    arr   0  1   
    if len(arr)<=1:
        return arr
    sorted_arr=[]
    while arr:
        idx=select_smallest(arr)
        sorted_arr.append(arr.pop(idx))
    return sorted_arr
        
arr=[random.randint(0,10) for i in range(0,10)]
print('original arr',arr)
print('sorted arr',selection_sort(arr))