C++에서 복사 대 수동 복사 배열

Question

수천 개의 레코드 배열을 정렬해야합니다. 나는 매번 새로운 레코드를 올바른 위치에 배치하므로 배열의 나머지 레코드 인덱스를 변경해야합니다. 내가 좋아하는 수동으로 실시로합니다

db[j]=record; 
    cout<<tmp.oName<<endl; 
    while (j++!=size-1){ 
     tmp2=db[j]; 
     db[j]=tmp; 
     tmp=db[j]; 
    } 

그리고 여기에 내 질문에 온다 : 그것은 새로운 배열과 사용 사본을 만들거나 내 현재 코드 옆에 눈에 띄는 컴퓨팅 시간과 메모리 사용량 개선이 없을 것입니다 훨씬 빠른 것? 저는 C++에 대해 매우 익숙합니다. 그래서이 함수가 어떻게 내부적으로 작동하는지 잘 모르겠습니다.

#include <iostream> 
#include <iomanip> 
#include <string> 
#include <cstring> 
#include <cstdlib> 
#include <cstdio> 

Answer 1

어레이 복사본을 만든 다음 복사하면 더 느려지고 더 많은 메모리를 사용합니다.

너는 N 개의 스폿이있는 배열이 있고 나는 새로운 아이템이 들어간 색인이라고 말한다. 배열을 복사한다는 것은 N 개의 추가 메모리를 사용하고 요소를 N 번 복사한다는 것을 의미합니다. 레코드를 단순히 이동하면 더 이상 메모리를 사용하지 않고 새 요소 다음에 요소를 이동하기 만하면 N-I 연산을 수행합니다.

Answer 2

당신이 STL을 사용할 수없는 경우, 당신의 case.Try 힙 정렬 또는 빠른 정렬에서 STL 데이터 구조를 확인하는 것이 좋습니다 :

내가 사용할 수 있습니다 포함되어 있습니다.

Answer 3

아니요. 새 배열을 만드는 것이 더 빠를 수는 없습니다. 거품 정렬을 사용하지 않는 것이 더 빠를 것입니다. 대신 빠른 정렬과 같은 것을 사용하십시오. 그냥 구글 빠른 정렬 C + +를 거기에 백 가지 예제를 볼 수 있습니다.

Answer 4

STL 컨테이너 및 알고리즘을 사용할 수없는 경우에도 벡터에 레코드를 넣은 다음 자신의 퀵 정렬 또는 병합 정렬을 사용할 수 있습니다. 빠른 정렬은 버블 정렬 또는 선택 정렬보다 효율적입니다. 참고로

: 당신이 당신의 자신의 정렬 된 목록을 만들려고처럼

http://www.algolist.net/Algorithms/Sorting/Quicksort

Answer 5

소리가 난다.

삽입 후 요소를 이동시키는 현재 코드가 배열에 삽입 할 때 수행 할 수있는 최상의 방법입니다. 목록의 용량을 변경하려면 현재 배열에서 공간이 부족할 때마다 새 배열을 만들어야합니다.

편집 :

이 (링크 목록에 반대) 배열 기반 목록을 사용하여 비용 중 하나입니다 - 삽입은 선형 시간 O (N)를 취

Answer 6

당신은 실제 생활을 위해 필요한 경우 , STL qsort (http://www.cplusplus.com/reference/cstdlib/qsort/)를 사용하십시오. 숙제가 필요하면 malloc을 실행할 시간 때문에 새로운 배열을 만드는 데 많은 비용이 듭니다.

Answer 7

삽입 지점에서 위쪽으로 이동하는 대신 위쪽에서 아래쪽으로 이동하도록 루프를 변경하면 코드가 훨씬 빨라집니다. 이 변경으로 인해 3 대신에 각 위치에 대해 하나의 사본 만 작성하면됩니다.

Answer 8

다른 게시물에서 언급했듯이 동일한 배열 내에서 삽입하는 것은 매번 전체 배열을 복사하는 것보다 빠릅니다.

한편, 삽입하는 방법은 삽입 정렬과 유사합니다. 하나의 삽입 작업으로 O (n) 비용이들 것입니다.힙을 사용하여 배열을 관리하면 삽입 비용은 O (log n)가되지만 작은 배열 크기에서는 느려질 수 있습니다. http://en.wikipedia.org/wiki/Binary_heap