kod1
unknown
c_cpp
3 years ago
3.9 kB
4
Indexable
#include <iostream> #include <string> #include <cmath> #include <bits/stdc++.h> #include <chrono> #include <fstream> using namespace std; void wybor(int tab[],int n) { int najmniejszy; for(int i=0;i<n;i++) //pętla zewnętrzna { najmniejszy = i; for(int j=i+1;j<n;j++) { //pętla wewnętrzna, szukająca najmniejszej liczby na miejsce i if(tab[j]<tab[najmniejszy]) najmniejszy = j; } swap(tab[i], tab[najmniejszy]); } } void babelkowe(int tab[], int n) { for(int i=0;i<n;i++) //zewnętrzna pętla, przejdzie przez każdy element tablicy for(int j=1;j<n;j++) //wewnętrzna pętla if(tab[j-1]>tab[j]) swap(tab[j-1], tab[j]); //zamiana miejscami } void wstawianie(int tab[], int n) { int pomoc, j; for(int i=1; i<n; i++) {//pętla zewnętrzna pomoc = tab[i]; j=i-1; while(j>=0&&tab[j]<pomoc) { //pętla odpowiadająca za wstawianie liczny w odpowiednie miejsce tab[j+1] = tab[j]; j = j-1; } tab[j+1] = pomoc; } } void quicksort(int tab[], int lewa, int prawa) { int i = lewa; int j = prawa; int x = tab[j]; //pivot = ostatni element do { //dopóki i<=j wykonaj while(tab[i]<x) //dopóki element o indeksie i jest mniejszy od pivota: i++; //dodaj 1 do i while(tab[j]>x) //dopóki element o indeksie j jest większy od pivota: j--; //odejmij 1 od j if(i<=j) { //jeżel i <= j to: swap(tab[i], tab[j]); //zamień elementy o indeksach i oraz j ze sobą i++; //dodaj 1 do i j--; //odejmij 1 od j } } while(i<=j); if(lewa<j) quicksort(tab, lewa, j); //rekurencja if(prawa>i) quicksort(tab, i, prawa); //rekurencja } void merge(int tab[], int lewy, int srodek, int prawy) { int pomoc[prawy + 1]; //tablica pomoc, będziemy umieszczali w jej posortowane elementy int i = lewy; int j = srodek + 1; int k = 0; while (i <= srodek && j <= prawy) { if (tab[i] <= tab[j]) { pomoc[k] = tab[i]; k++; i++; } else { pomoc[k] = tab[j]; k++; j++; } } while (i <= srodek) { pomoc[k] = tab[i]; k++; i++; } while (j <= prawy) { pomoc[k] = tab[j]; k++; j++; } k--; while (k >= 0) { tab[k + lewy] = pomoc[k]; k--; } } void mergesort(int tab[],int lewy, int prawy) { if(prawy<=lewy) return; int srodek = (prawy+lewy)/2; mergesort(tab, lewy, srodek); mergesort(tab, srodek+1, prawy); merge(tab, lewy, srodek, prawy); } int main() { int n = 2000; //ZMIANA ROZMIARU ZBIORU// int tab[n]; fstream file; file.open("C:\\Users\\macie\\Desktop\\porownanie_al_sort\\pes_2000liczb.txt"); //ZMIANA PLIKU// for(int i=0; i<n; i++) { file >> tab[i]; } file.close(); // POCZĄTEK POMIARU CZASU // auto start2 = chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(false); //************************// // SORTOWANIE // //wybor(tab, n); babelkowe(tab, n); //wstawianie(tab, n); //quicksort(tab, 0, n-1); //mergesort(tab, 0, n-1); //************// // ZWRÓCENIE POMIARU CZASU // auto end2 = chrono::high_resolution_clock::now(); //koniec double time_taken2 = chrono::duration_cast<chrono::nanoseconds>(end2 -start2).count(); time_taken2 *= 1e-9; //konwersja ns s → cout << fixed << "czas : " << time_taken2 << setprecision(9); cout << " sec" << endl; //*************************// // ZWRÓCENIE POSORTOWANEJ TABLICY // //for(int i=0; i<n; i++) { // cout << tab[i] << " "; //} //*************************// }
Editor is loading...