찾다
백엔드 개발C++C에서 병합 정렬의 최악의 시나리오로 이어지는 순열을 찾으십시오.

C에서 병합 정렬의 최악의 시나리오로 이어지는 순열을 찾으십시오.

Concept

주어진 요소 집합에 대해 어떤 배열이 병합 정렬의 최악의 경우로 이어질지 결정합니까?

점근적으로 병합 정렬은 항상 O(n log n) 시간이 걸리지만 실제로는 더 많은 비교가 필요한 경우에는 일반적으로 더 많은 시간이 걸립니다. 이제 기본적으로 일반적인 병합 정렬 알고리즘을 구현할 때 비교 횟수를 최대화하는 입력 요소 배열을 결정해야 합니다.

다음 요소 집합을 정렬된 배열로 간주합니다. 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

최악의 병합 정렬로 이어지는 입력 배열은 11 19 15 23입니다. 13 21 17 25 12 20 16 24 14 22 18 26

Method

병합 정렬을 위한 최악의 입력 집합을 구축하는 방법을 연구합니다.

이제 우리는 상향식 방식으로 배열을 구축하려고 합니다.

이제 정렬된 배열을 {11, 12, 13, 14, 15, 16, 17, 18}로 둡니다.

병합 정렬에 대한 최악의 시나리오를 구성하려면 위의 정렬된 배열을 초래하는 병합 작업에서 가장 많은 비교가 발생해야 합니다. 따라서 병합 작업에 참여하는 왼쪽 하위 배열과 오른쪽 하위 배열은 정렬된 배열의 요소를 교대로 저장해야 하며, 왼쪽 하위 배열은 {11, 13, 15, 17}, 오른쪽 하위 배열은 {12, 14, 16이어야 합니다. , 18 }. 이렇게 하면 배열의 각 요소가 최소한 한 번 비교되어 최대 비교 횟수가 발생합니다. 이제 왼쪽 하위 배열과 오른쪽 하위 배열에도 동일한 논리를 구현합니다. 배열 {11, 13, 15, 17}의 경우 왼쪽 하위 배열이 {11, 15}이고 오른쪽 하위 배열이 {12, 14, 16, 18}인 경우 최악의 경우가 발생합니다. , 최악의 경우는 {12, 14} 및 {16, 18}에서 발생합니다.

Full Algorithm

GenerateWorstCase(arr[])

  • 이제 왼쪽과 오른쪽에 두 개의 보조 배열을 만들고 그 안에 교대로 배열 요소를 저장합니다.

  • GenerateWorstCase - 왼쪽 하위 배열을 호출합니다.

  • 오른쪽 하위 배열에서 generateWorstCase - 생성WorstCase(오른쪽)를 호출합니다.

  • 이제 왼쪽 하위 배열과 오른쪽 하위 배열의 모든 요소를 ​​복사합니다. 원래 배열을 반환합니다.

데모

// C program to generate Worst Case of Merge Sort
#include <stdlib.h>
#include <stdio.h>
// Indicates function to print an array
void printArray(int A1[], int size1){
   for (int i = 0; i < size1; i++)
      printf("%d ", A1[i]);
   printf("</p><p>");
}
// Indicates function to join left and right subarray
int join(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
   int i; // So used in second loop
   for (i = 0; i <= m1 - l1; i++)
      arr1[i] = left1[i];
   for (int j = 0; j < r1 - m1; j++)
      arr1[i + j] = right1[j];
}
// Indicates function to store alternate elemets in left
// and right subarray
int split(int arr1[], int left1[], int right1[],
int l1, int m1, int r1){
   for (int i = 0; i <= m1 - l1; i++)
      left1[i] = arr1[i * 2];
   for (int i = 0; i < r1 - m1; i++)
      right1[i] = arr1[i * 2 + 1];
}
// Indicates function to generate Worst Case of Merge Sort
int generateWorstCase(int arr1[], int l1, int r1){
   if (l1 < r1){
      int m1 = l1 + (r1 - l1) / 2;
      // creating two auxillary arrays
      int left1[m1 - l1 + 1];
      int right1[r1 - m1];
      // Storing alternate array elements in left
      // and right subarray
      split(arr1, left1, right1, l1, m1, r1);
      // Recursing first and second halves
      generateWorstCase(left1, l1, m1);
      generateWorstCase(right1, m1 + 1, r1);
      // joining left and right subarray
      join(arr1, left1, right1, l1, m1, r1);
   }
}
// Driver code
int main(){
   // Initializes sorted array
   int arr1[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 };
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   printf("Sorted array is </p><p>");
   printArray(arr1, n1);
   // generating worst Case of Merge Sort
   generateWorstCase(arr1, 0, n1 - 1);
   printf("</p><p>Input array that will result in " "worst case of merge sort is </p><p>");
   printArray(arr1, n1);
   return 0;
}

출력

Sorted array is
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Input array that will result in worst case of merge sort is
11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

위 내용은 C에서 병합 정렬의 최악의 시나리오로 이어지는 순열을 찾으십시오.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
이 기사는 tutorialspoint에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제
C : 죽어 가거나 단순히 진화하고 있습니까?C : 죽어 가거나 단순히 진화하고 있습니까?Apr 24, 2025 am 12:13 AM

c is nontdying; it'sevolving.1) c COMINGDUETOITSTIONTIVENICICICICINICE INPERFORMICALEPPLICATION.2) thelugageIscontinuousUllyUpdated, witcentfeatureslikemodulesandCoroutinestoimproveusActionalance.3) despitechallen

C 현대 세계에서 : 응용 및 산업C 현대 세계에서 : 응용 및 산업Apr 23, 2025 am 12:10 AM

C는 현대 세계에서 널리 사용되고 중요합니다. 1) 게임 개발에서 C는 Unrealengine 및 Unity와 같은 고성능 및 다형성에 널리 사용됩니다. 2) 금융 거래 시스템에서 C의 낮은 대기 시간과 높은 처리량은 고주파 거래 및 실시간 데이터 분석에 적합한 첫 번째 선택입니다.

C XML 라이브러리 : 옵션 비교 및 ​​대조C XML 라이브러리 : 옵션 비교 및 ​​대조Apr 22, 2025 am 12:05 AM

C : Tinyxml-2, Pugixml, XERCES-C 및 RapidXML에는 4 개의 일반적으로 사용되는 XML 라이브러리가 있습니다. 1. TINYXML-2는 자원이 제한적이고 경량이지만 제한된 기능을 가진 환경에 적합합니다. 2. PugixML은 빠르며 복잡한 XML 구조에 적합한 XPath 쿼리를 지원합니다. 3.xerces-c는 강력하고 DOM 및 SAX 해상도를 지원하며 복잡한 처리에 적합합니다. 4. RapidXML은 성능에 중점을두고 매우 빠르게 구문 분석하지만 XPath 쿼리를 지원하지는 않습니다.

C 및 XML : 관계와 지원 탐색C 및 XML : 관계와 지원 탐색Apr 21, 2025 am 12:02 AM

C는 XML과 타사 라이브러리 (예 : TinyXML, Pugixml, Xerces-C)와 상호 작용합니다. 1) 라이브러리를 사용하여 XML 파일을 구문 분석하고 C- 처리 가능한 데이터 구조로 변환하십시오. 2) XML을 생성 할 때 C 데이터 구조를 XML 형식으로 변환하십시오. 3) 실제 애플리케이션에서 XML은 종종 구성 파일 및 데이터 교환에 사용되어 개발 효율성을 향상시킵니다.

C# vs. C : 주요 차이점과 유사성 이해C# vs. C : 주요 차이점과 유사성 이해Apr 20, 2025 am 12:03 AM

C#과 C의 주요 차이점은 구문, 성능 및 응용 프로그램 시나리오입니다. 1) C# 구문은 더 간결하고 쓰레기 수집을 지원하며 .NET 프레임 워크 개발에 적합합니다. 2) C는 성능이 높고 시스템 프로그래밍 및 게임 개발에 종종 사용되는 수동 메모리 관리가 필요합니다.

C# vs. C : 역사, 진화 및 미래 전망C# vs. C : 역사, 진화 및 미래 전망Apr 19, 2025 am 12:07 AM

C#과 C의 역사와 진화는 독특하며 미래의 전망도 다릅니다. 1.C는 1983 년 Bjarnestroustrup에 의해 발명되어 객체 지향 프로그래밍을 C 언어에 소개했습니다. Evolution 프로세스에는 자동 키워드 소개 및 Lambda Expressions 소개 C 11, C 20 도입 개념 및 코 루틴과 같은 여러 표준화가 포함되며 향후 성능 및 시스템 수준 프로그래밍에 중점을 둘 것입니다. 2.C#은 2000 년 Microsoft에 의해 출시되었으며 C와 Java의 장점을 결합하여 진화는 단순성과 생산성에 중점을 둡니다. 예를 들어, C#2.0은 제네릭과 C#5.0 도입 된 비동기 프로그래밍을 소개했으며, 이는 향후 개발자의 생산성 및 클라우드 컴퓨팅에 중점을 둘 것입니다.

C# vs. C : 학습 곡선 및 개발자 경험C# vs. C : 학습 곡선 및 개발자 경험Apr 18, 2025 am 12:13 AM

C# 및 C 및 개발자 경험의 학습 곡선에는 상당한 차이가 있습니다. 1) C#의 학습 곡선은 비교적 평평하며 빠른 개발 및 기업 수준의 응용 프로그램에 적합합니다. 2) C의 학습 곡선은 가파르고 고성능 및 저수준 제어 시나리오에 적합합니다.

C# vs. C : 객체 지향 프로그래밍 및 기능C# vs. C : 객체 지향 프로그래밍 및 기능Apr 17, 2025 am 12:02 AM

C# 및 C가 객체 지향 프로그래밍 (OOP)의 구현 및 기능에 상당한 차이가 있습니다. 1) C#의 클래스 정의 및 구문은 더 간결하고 LINQ와 같은 고급 기능을 지원합니다. 2) C는 시스템 프로그래밍 및 고성능 요구에 적합한 더 미세한 입상 제어를 제공합니다. 둘 다 고유 한 장점이 있으며 선택은 특정 응용 프로그램 시나리오를 기반으로해야합니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

MinGW - Windows용 미니멀리스트 GNU

MinGW - Windows용 미니멀리스트 GNU

이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.

mPDF

mPDF

mPDF는 UTF-8로 인코딩된 HTML에서 PDF 파일을 생성할 수 있는 PHP 라이브러리입니다. 원저자인 Ian Back은 자신의 웹 사이트에서 "즉시" PDF 파일을 출력하고 다양한 언어를 처리하기 위해 mPDF를 작성했습니다. HTML2FPDF와 같은 원본 스크립트보다 유니코드 글꼴을 사용할 때 속도가 느리고 더 큰 파일을 생성하지만 CSS 스타일 등을 지원하고 많은 개선 사항이 있습니다. RTL(아랍어, 히브리어), CJK(중국어, 일본어, 한국어)를 포함한 거의 모든 언어를 지원합니다. 중첩된 블록 수준 요소(예: P, DIV)를 지원합니다.

Dreamweaver Mac版

Dreamweaver Mac版

시각적 웹 개발 도구

PhpStorm 맥 버전

PhpStorm 맥 버전

최신(2018.2.1) 전문 PHP 통합 개발 도구

맨티스BT

맨티스BT

Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.