kod1

 avatar
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...