알고리즘 정렬 : Bubblesort를 사용하지 않아야하는 이유 알아보기

폭로: 귀하의 지원은 사이트 운영을 유지하는 데 도움이됩니다! 이 페이지에서 권장하는 일부 서비스에 대한 추천 수수료가 발생합니다.


컴퓨터가 어떻게 물건을 정리하는지 궁금해 한 적이 있습니까? Excel에서 A-Z 버튼을 클릭하면 실제로 진행되는 작업?

컴퓨터는 “정렬 알고리즘”이라는 절차에 따라 목록을 정렬합니다. 알고리즘은 기계적으로 반복해서 수행 할 수있는 일련의 명령어입니다. 목록을 올바른 순서로 배치하는 절차는 여러 가지 정렬 알고리즘이 있습니다. 각각의 강점과 약점.

가장 인기있는 정렬 알고리즘은 다음과 같습니다..

버블 정렬

버블 정렬은 비효율적이지만 간단한 알고리즘입니다. 실제로는 거의 사용되지 않지만 이해하기 쉽습니다..

버블 정렬은 목록에서 요소의 연속 쌍을 비교하여 작동합니다. 첫 번째와 두 번째 요소, 두 번째와 세 번째, 세 번째와 네 번째 등이 목록을 통해 비교됩니다. 각 비교 후 두 요소가 고장난 경우 교체됩니다. 단일 반복 후 가장 큰 요소는 목록의 끝까지 “거품”입니다. 이 절차는 목록이 정렬 될 때까지 계속 반복됩니다..

양방향 변형에서, 목록을 통해 교대로 앞뒤로 목록을 비교합니다. 목록의 각 끝에서 정렬 된 섹션이 늘어납니다. 이것을 “칵테일 쉐이커 종류”라고도합니다.

버블 정렬을 사용하는 경우

시연을 제외하고는 절대로.

버블 정렬에 대한 추가 정보

  • 예제 코드와 함께 알고리즘에서 버블 정렬 설명;
  • 100 가지가 넘는 프로그래밍 언어로 코딩 된 Bubble Sort Algorithm;
  • 레고로 설명 된 버블 정렬;
  • 헝가리 민속 무용 일러스트 버블 정렬.

삽입 정렬

삽입 정렬은 대부분의 사람들이 종이를 알파벳 순으로 정렬 할 때와 같이 직관적으로 수동으로 정렬하는 방법입니다. 각 요소를 차례대로 이미 정렬 된 부분 내에서 적절한 위치로 이동시키는 과정.

목록의 첫 번째 요소는 “정렬 된”것으로 간주됩니다. 그런 다음 두 번째 요소가 고려됩니다. 이전 요소보다 큰 경우 올바른 위치에 있으며 “정렬 된”섹션의 일부를 형성합니다. 그렇지 않으면, 한 슬롯 뒤로 이동하여 뒤에있는 요소와 비교됩니다. 요소는 목록의 정렬 된 부분 내에서 올바른 위치에 올 때까지 뒤로 이동합니다. 그런 다음이 절차는 세 번째, 네 번째, 다섯 번째 요소 등으로 반복됩니다..

삽입 정렬을 사용하는 경우

삽입 정렬은 일반적으로 작은 목록 (10 개 이하의 요소)을 정렬하는 가장 빠른 솔루션이며, 중간 크기 목록에서 최소한 적절하게 수행됩니다. 그러나 큰 세트에서는 엄청나게 느려질 수 있습니다..

삽입 정렬은 목록이 이미 대부분 정렬되어있는 경우에도 큰 집합에서도 잘 수행됩니다. 따라서 레거시 사람 정렬 데이터를 정리하거나 다른 정렬 알고리즘과 함께 사용하는 데 이상적입니다. 예를 들어, 빠른 정렬로 시작한 다음 몇 번의 반복 후에 삽입 정렬로 전환하는 것이 일반적입니다..

삽입 정렬에 대한 추가 정보

  • 칸 아카데미에서 삽입 설명과 코딩 연습;
  • 거의 100 개의 다른 프로그래밍 언어로 코딩 된 삽입 정렬 알고리즘;
  • 삽입 정렬 스티로폼 컵으로 설명하고 하버드 CS 학생이 내레이션합니다.
  • 헝가리 민속 무용 삽화 삽입 삽입.

힙 정렬

힙 정렬은 이진 힙 데이터 구조를 목록의 요소에 대한 중간 홀더로 사용하는 두 부분으로 구성된 정렬입니다..

이진 힙은 각 노드에 최대 두 개의 자식 노드가있는 트리 구조입니다. 가장 큰 요소는 트리의 맨 위에 있습니다. 각 자식 노드는 부모 노드보다 작습니다. 이는 힙을 작성하는 프로세스가 목록을 부분적으로 정렬 함을 의미합니다. 힙이 구축되면 가장 큰 요소가 제거되고 정렬 된 배열에 배치됩니다 (그 다음에 나머지 힙 중 가장 큰 것 등)..

힙 정렬을 사용하는 경우

평균적으로 힙 정렬은 우수한 성능을 제공합니다. 또한 최악의 시나리오는 거의 모든 다른 알고리즘의 최악의 시나리오보다 훨씬 낫습니다. 따라서 대규모 및 분산 데이터 세트와 함께 자주 사용됩니다..

힙 정렬에 대한 추가 정보

  • Kent State의 CS 교수의 힙 정렬에 대한 자세한 설명;
  • MIT의 힙 및 힙 정렬 비디오 강의;
  • 힙 및 힙 정렬에 대한 자세한 내용은이 5 부 비디오 시리즈를 참조하십시오..

정렬 병합

이미 정렬 된 두 목록을 이미 정렬 된 새 목록으로 병합하는 것은 비교적 간단합니다. 각 요소의 첫 번째 요소를 비교하고 새 목록에 작은 요소를 배치하고 반복하십시오. 이것이 병합 정렬의 기초입니다.

병합 정렬을 시작하기 위해 목록은 1 요소 “목록”으로 나뉩니다. 그런 다음이 목록의 쌍은 2 요소 목록으로 병합 된 다음 전체 목록이 다시 병합 될 때까지 4 요소 목록으로 병합됩니다..

병합 정렬을 사용하는 경우

병합 정렬은 매우 효율적입니다. 유일한 문제는 병합 정렬에는 일반적으로 목록을 두 번 보유하기에 충분한 활성 메모리 (RAM)가 필요하다는 것입니다. 따라서 특정 상황에서는 실현 불가능할 수 있습니다.

병합 정렬에 대한 추가 정보

  • Khan Academy의 Merge Sort는 프로그래밍 연습이 포함 된 훌륭한 6 부 수업입니다.
  • 80 가지가 넘는 프로그래밍 언어로 정렬 된 병합 정렬;
  • German Folk Dance와 정렬 병합은 정렬 알고리즘을 보여주는 댄스 루틴을 제공합니다.

빠른 정렬

빠른 정렬은 그리 직관적이지 않습니다. 그러나 매우 효율적입니다..

빠른 정렬의 첫 번째 단계는 피벗 요소를 선택하는 것입니다. 이것은 목록의 모든 요소가 될 수 있습니다. 다음으로, 피벗보다 큰 모든 값은 피벗 뒤에 배치되고, 모든 값은 피벗보다 앞에 배치됩니다. 이렇게하면 두 개의 파티션이 만들어 지지만 서로 정렬되지는 않습니다. 각 파티션에서 동일한 절차가 수행 된 다음 각 하위 파티션에서 수행됩니다. 파티션이 각각 한 요소의 크기에 도달하면 목록이 정렬됩니다.

빠른 정렬을 사용하는 경우

빠른 정렬은 실용적으로 가장 많이 사용되는 정렬 알고리즘 중 하나입니다. 평균 속도가 매우 빠릅니다. 그러나 최악의 시나리오 (자연 데이터 세트에서는 거의 발생하지 않음)가 매우 큰 세트에서 문제가됩니다..

빠른 정렬에 대한 추가 정보

  • 100 개 이상의 프로그래밍 언어로 코딩 된 빠른 정렬;
  • 빠른 정렬 하버드 CS-50 클래스의 블록으로 설명;
  • 자습서의 빠른 정렬 자습서 Point에는 많은 세부 정보, 샘플 코드 및 애니메이션 이미지가 있습니다..

일반적인 정렬 알고리즘 리소스

  • 데이터 구조-정렬 기법은 Tutorials Point의 매우 상세한 시리즈입니다.
  • 정렬 알고리즘에는 다양한 조건 하에서 모든 종류의 시각화가 있습니다. 서로 다른 알고리즘이 서로 경쟁하는 것을 볼 수도 있습니다.
  • 6 분 안에 알고리즘 정렬은 매혹적인 비디오 시각화입니다.
  • 정렬은 컴퓨터 화 된 정렬 문제를 탐색하는 비디오입니다.
  • 다른 정렬 알고리즘의 사운드는 몇 가지 정렬 알고리즘을 사운드로 변환하는 놀라운 “감사”비디오입니다..

요약

대부분의 경우 프로그래밍 할 때 간단한 정렬 값 (짧은 값 배열, 데이터 열)이 필요한 경우 프로그래밍 언어 또는 즐겨 사용하는 라이브러리에 내장 된 방법이나 함수 만 사용하면됩니다..

그러나 대규모 데이터 응용 프로그램에서 작업 할 때는 선택한 알고리즘이 시스템 성능에 어떤 영향을 미치는지 고려해야합니다. 그 외에도 분류 알고리즘은 컴퓨터 과학의 기본 요소이며 개발 또는 프로그래밍 분야의 모든 사람이 잘 이해해야합니다..

추가 자료 및 자료

코딩 및 개발과 관련된 더 많은 가이드, 자습서 및 인포 그래픽이 있습니다.

  • C ++ 개발자 리소스 : 가장 널리 사용되는 프로그래밍 언어 중 하나이며 대부분의 응용 프로그램에 적합.
  • 유니 코드 소개 및 리소스 : 문자 인코딩에 대한 모든 정보.
  • MantisBT 소개 및 리소스 : MantisBT는 가장 인기있는 버그 추적 프로그램 중 하나입니다..

어떤 코드를 배워야합니까?

코딩해야 할 프로그래밍 언어에 대해 혼란 스러우십니까? 인포 그래픽, 어떤 코드를 배워야합니까?를 확인하십시오. 언어의 다양한 측면에 대해서만 논의 할뿐만 아니라“생활에 필요한 Java를 얼마만큼 돈을 벌 수 있을까요?”와 같은 중요한 질문에 답변합니다.

어떤 코드를 배워야합니까?
어떤 코드를 배워야합니까?

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me
    Like this post? Please share to your friends:
    Adblock
    detector
    map