Sortowanie wstępne elementów

0

Witam,
mój problem wiąże się z sortowaniem wstępnym. Moim zadaniem jest napisanie sortowań mergesort, quicksort i introsort (elementy tablicy generowane randem ) oraz wykonać ich testy efektywności dla [0, 25, 50, 75, 95, 99, 99,7]% elementów posortowanych. Sortowania mam już zrobione, działają poprawnie, ale nie mogę sobie poradzić z sortowaniem wstępnym... Należy posortować np. 50% elementów, a resztę tablicy zostawić w "rozsypce". Chodzi mi o takie coś (przy tablicy 10 elementowej):
[98 23 41 84 37 7 12 43 55 75] -> [7, 12, 23, 37, 41, | 98, 84, 43, 55, 77] (lub ostatnie 5 w dowolnej kolejności)

Czyli sortowanie tylko najmniejszych wartości z całej tablicy. Niestety mam posortować 100 tablic po milion elementów, więc liczenie średniej (w sumie jedyny sensowny pomysł jaki mi przyszedł do głowy) raczej nie zda tutaj egzaminu. Mogę także "zbudować" np 50%, posortować a następnie "dopisać" resztę elementów losując od ostatniego elementu. Teoretycznie można także określić dla miliona elementów ten próg na stałe (tj. ćwierć/pół miliona) ale wtedy nie mam pewności, że posortuje się dokładnie te 25/50%...
Czy robił ktoś coś podobnego? Macie może jakiś pomysł? Nie szukam oczywiście gotowca, a jedynie jakiegoś sposobu/algorytmu/wskazówek jak można to zrobić.

Pozdrawiam, Michał

0
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;
int main()
{
        srand(time(NULL));
        vector <int> a;
        int c,b=10;
        for(int i=0;i!=b;i++)
        {
                cin>>c;
                a.push_back(c);
        }
        sort(a.begin(),a.end());
        random_shuffle(a.begin()+(b/2),a.end());
 
        for(int i=0;i!=a.size();i++)
        cout<<a[i]<<" ";
        cin.ignore();
        getchar();
        return 0;
}

a - vector liczb,
b - ilosc liczb do posortowania
c - pomocnicza do zapisywania elementow do wektora

0

Dziękuję bardzo za szybką odpowiedź :)

0

50% posortowanych danych oznacza że 50% z nich nie ma "złych" poprzedników.
Ale nie oznacza (nie powinno) że to jest pierwsza czy druga połówka posortowana.

Ważne ze względu na to że quicksort najgorszą efektywność uzyskuje przy posortowanych(!) danych.

0
vpiotr napisał(a):

50% posortowanych danych oznacza że 50% z nich nie ma "złych" poprzedników.
Ale nie oznacza (nie powinno) że to jest pierwsza czy druga połówka posortowana.

Ważne ze względu na to że quicksort najgorszą efektywność uzyskuje przy posortowanych(!) danych.

W takim razie:

int dl=a.size()/2;
int p=rand()%dl;
random_shuffle(a.begin()+p,a.begin()+p+dl);

 

1 użytkowników online, w tym zalogowanych: 0, gości: 1