정렬된 배열

정렬된 배열
유형	어레이
발명된	1945
발명자	요한 폰 노이만
빅 O 표기의 시간 복잡도
알고리즘. 평균 최악의 경우 공간 O(n) O(n) 서치 O(log n) O(log n) 삽입 O(n) O(n) 삭제 O(n) O(n)

정렬된 배열은 각 요소가 숫자, 알파벳 또는 기타 순서로 정렬되어 컴퓨터 메모리의 동일한 간격의 주소에 배치되는 배열 데이터 구조입니다.일반적으로 컴퓨터 과학에서 동일한 데이터 유형을 가진 여러 값을 유지하는 정적 조회 테이블을 구현하기 위해 사용됩니다.배열 정렬은 데이터를 순서대로 정리하고 신속하게 복구할 때 유용합니다.

방법들

배열 정렬에는 선택 정렬, 버블 정렬, 삽입 정렬, 병합 정렬, Quicksort, Humpsort 및 ^{[citation needed]}Counting 정렬 등 많은 알려진 방법이 있습니다.이러한 정렬 기법에는 서로 다른 알고리즘이 관련되어 있으므로 각 방법을 사용하면 여러 가지 이점이 있습니다.

개요

정렬된 배열은 순차적으로 저장된 ^{[citation needed]}데이터에 가장 적합한 참조 인접성을 갖춘 공간 효율적인 데이터 구조입니다.

정렬된 배열 내의 요소는 O(log n)에서 바이너리 검색을 사용하여 검색되므로 정렬된 배열은 예를 들어 세트 또는 멀티셋 데이터 구조처럼 요소를 신속하게 검색할 필요가 있는 경우에 적합합니다.룩업의 복잡성은 자가 밸런싱 바이너리 검색 트리의 복잡성과 동일합니다.

일부 데이터 구조에서는 구조 배열이 사용됩니다.이 경우 구조 요소와 같은 키에 따라 구조물을 정렬하는 동일한 정렬 방법을 사용할 수 있다. 예를 들어 롤 번호, 이름 또는 성적에 따라 학생의 기록을 정렬하는 것이다.

정렬된 동적 배열을 사용하는 경우 요소를 삽입 및 삭제할 수 있습니다.소트된 배열 내의 요소 삽입 및 삭제는 삽입 또는 삭제할 요소에 이어 모든 요소를 이동해야 하므로 O(n)에서 실행됩니다. 이에 비해 자기 밸런싱 바이너리 검색 트리는 O(log n)에서 삽입 및 삭제합니다.요소가 마지막에 삭제 또는 삽입된 경우, 자기 밸런싱 바이너리 서치 트리가 항상 O(log n)로 동작하는 동안 정렬된 동적 어레이는 상각된 O(1) 시간 내에 이를 수행할 수 있다.

정렬된 배열 내의 요소는 O(1) 시간에 인덱스(랜덤 액세스)에 의해 검색될 수 있으며, 보다 복잡한 데이터 구조에 대해서는 O(log n) 또는 O(n) 시간이 걸리는 조작이다.

역사

John von Neumann은 최초의 저장 프로그램 컴퓨터가 ^[1]아직 제조되고 있던 1945년에 최초의 배열 정렬 프로그램(머지 정렬)을 작성했습니다.

정렬된 어레이의 응용 프로그램

비지니스용^[2] 컴퓨팅

정부 기관, 민간 기업 및 많은 웹 기반 애플리케이션은 막대한 양의 데이터를 처리해야 합니다.데이터에 여러 번 액세스해야 하는 경우가 많습니다.데이터를 정렬된 형식으로 유지하면 빠르고 쉽게 검색할 수 있습니다.

이산 수학에서

정렬된 배열은 Dijkstra 알고리즘 또는 Prim 알고리즘을 구현하는 데 사용할 수 있습니다.또한 최소한의 스패닝 트리를 찾는 Kruskal 알고리즘과 같은 알고리즘도 있습니다.

priority 스케줄링 중

운영 체제 수준에서는 한 번에 여러 프로세스가 보류 중이지만 한 번에 처리할 수 있는 프로세스는 1개뿐입니다.따라서 우선순위는 각 공정과 관련되어 있습니다.다음으로 프로세스 ID의 정렬된 배열을 사용하여 가장 높은 우선순위에 따라 프로세스가 CPU로 전송됩니다.여기서는 우선순위에 따라 프로세스가 정렬되고 CPU가 할당됩니다.정렬된 배열에서는 우선순위가 가장 높은 프로세스가 첫 번째 위치를 차지합니다.따라서 우선순위에 따른 시스템프로세스 스케줄링이 이루어집니다.^[3]

최단 작업 우선 스케줄링

이것은 priority 스케줄링의 특수한 경우입니다.여기서 프로세스는 프로세스의 버스트 시간에 따라 정렬됩니다.가장 짧은 시간을 필요로 하는 프로세스에 먼저 CPU가 할당됩니다.따라서 프로세스는 버스트 시간에 따라 CPU로 전송됩니다.

과정	버스트 시간
P1	3
P2	4
P3	1
P4	8
P5	6

「 」를 참조해 주세요.

• 정렬 알고리즘
• 이진 검색 알고리즘
• 힙(데이터 구조)
• 검색 데이터 구조

레퍼런스