Results 1 to 7 of 7

Hybrid View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Street Racer Rain9333's Avatar
    Join Date: Feb:2007
    Location: Bg, Gb
    Posts: 824

    Quick & Merge Sort

    , quicksort merge sort, , 348 . 0 . , 348 . / ?
    #include<process.h>
    #include<iostream>
    #include<conio.h>
    #include<stdlib.h>
    #include <ctime>
    clock_t qn,qk,mn,mk ;
    double q,m ;
    using namespace std ;

    int *a,n,low,high,i;

    void merge(int,int,int);
    void merge_sort(int low,int high)
    { mn = clock () ;
    int mid;
    if(low<high)
    {
    mid=(low+high)/2;
    merge_sort(low,mid);
    merge_sort(mid+1,high);
    merge(low,mid,high);
    } mk = clock () ;
    }


    int Partition(int low,int high,int arr[]);
    void Quick_sort(int low,int high,int arr[]);

    int main()
    {
    cout<<"Vyvedete broqt na elementite :";
    cin>>n;

    a=new int[n];
    for(i=0;i<n;i++)
    a[i]=rand()% 100000 + 1;

    cout<<"Na4alnite elementi sa :"<<endl;
    for(i=0;i<n;i++)
    cout<<a[i]<<" ";
    cout<<" ";

    high=n-1;
    low=0;

    Quick_sort(low,high,a);

    cout<<endl<<"Sortirane 4rez QuickSort :"<<endl;

    for(i=0;i<n;i++)
    cout<<a[i]<<" ";

    merge_sort(1,n);

    cout<<endl<<"Sortirane 4rez MergeSort :"<<endl;

    for(i=0;i<n;i++)
    cout<<a[i]<<" ";

    cout<<endl;
    q = difftime (qk,qn) ;
    m = difftime (mk,mn) ;
    q = q / 1000 ; m = m / 1000 ;
    cout <<"Vremeto za sortirane 4rez QuickSort e : " << q <<" sekundi."<<endl ;
    cout <<"Vremeto za sortirane 4rez MergeSort e : " << m <<" sekundi."<<endl ;

    getch();
    return 0 ;
    }


    int Partition(int low,int high,int arr[])
    { int i,high_vac,low_vac,pivot;
    pivot=arr[low];
    while(high>low)
    { high_vac=arr[high];

    while(pivot<high_vac)
    {
    if(high<=low) break;
    high--;
    high_vac=arr[high];
    }

    arr[low]=high_vac;
    low_vac=arr[low];
    while(pivot>low_vac)
    {
    if(high<=low) break;
    low++;
    low_vac=arr[low];
    }
    arr[high]=low_vac;
    }
    arr[low]=pivot;
    return low;
    }

    void Quick_sort(int low,int high,int arr[])
    {qn = clock () ;
    int Piv_index,i;
    if(low<high)
    {
    Piv_index=Partition(low,high,arr);
    Quick_sort(low,Piv_index-1,arr);
    Quick_sort(Piv_index+1,high,arr);
    } qk = clock () ;
    }


    void merge(int low,int mid,int high)
    {
    int h,i,j,c[n],k;
    h=low;
    i=low;
    j=mid+1;

    while((h<=mid)&&(j<=high))
    {
    if(a[h]<=a[j]) {
    c[i]=a[h];
    h++;
    }
    else
    {
    c[i]=a[j];
    j++; }
    i++;
    }
    if(h>mid)
    {
    for(k=j;k<=high;k++) {
    c[i]=a[k];
    i++; }
    }
    else
    {
    for(k=h;k<=mid;k++) {
    c[i]=a[k];
    i++; }
    }
    for(k=low;k<=high;k++) a[k]=c[k];
    }
    MSI X570-A PRO, AMD 5800X3D, Noctua NH-D15, Corsair Vengeance LPX 2x8GB-3600, ASUS RTX ROG 3080 Strix White OC, Samsung 980 Pro 1TB NVMe, Corsair RM750, FD Define R5, Dell 32" 4k G3223Q 144Hz + 3xSamsung G5 32" 144hz, SimLab P1-X, Simucube 2 Pro, HE Ultimate, SRB GT3 Wheel

  2. #2
    Registered User tedych's Avatar
    Join Date: Nov:2003
    Location:
    Posts: 17,654
    , .
    348 ?

  3. #3
    Street Racer Rain9333's Avatar
    Join Date: Feb:2007
    Location: Bg, Gb
    Posts: 824
    Quote Originally Posted by tedych View Post
    , .
    348 ?
    , ,
    500 000 600 000 Send - Don't Send error
    Last edited by Rain9333; 16th April 2009 at 12:53.
    MSI X570-A PRO, AMD 5800X3D, Noctua NH-D15, Corsair Vengeance LPX 2x8GB-3600, ASUS RTX ROG 3080 Strix White OC, Samsung 980 Pro 1TB NVMe, Corsair RM750, FD Define R5, Dell 32" 4k G3223Q 144Hz + 3xSamsung G5 32" 144hz, SimLab P1-X, Simucube 2 Pro, HE Ultimate, SRB GT3 Wheel

  4. #4
    Registered User
    Join Date: Dec:2007
    Location: Sofia
    Posts: 366

    1. - ( ).
    2. Quick_sort(), Quick_sort() -, -. - , Partition() .
    3. pivot . .

  5. #5
    Street Racer Rain9333's Avatar
    Join Date: Feb:2007
    Location: Bg, Gb
    Posts: 824
    , 50 . . , Visual C++, Dev-C++ ( ). :

    ? .
    ..:
    MSI X570-A PRO, AMD 5800X3D, Noctua NH-D15, Corsair Vengeance LPX 2x8GB-3600, ASUS RTX ROG 3080 Strix White OC, Samsung 980 Pro 1TB NVMe, Corsair RM750, FD Define R5, Dell 32" 4k G3223Q 144Hz + 3xSamsung G5 32" 144hz, SimLab P1-X, Simucube 2 Pro, HE Ultimate, SRB GT3 Wheel

  6. #6
    Registered User
    Join Date: Dec:2007
    Location: Sofia
    Posts: 366


    #pragma comment(linker, "/stack:10000000")

    Dev-C++ - , . , - , , - VC++2008, ..

  7. #7
    Street Racer Rain9333's Avatar
    Join Date: Feb:2007
    Location: Bg, Gb
    Posts: 824
    Quote Originally Posted by Pheoman View Post


    #pragma comment(linker, "/stack:10000000")

    Dev-C++ - , . , - , , - VC++2008, ..
    ( , (( , , ...)) ). , .

    #include <stdio.h>
    #include <stdlib.h>
    #include <ctime>
    #include <iostream>
    /* Pri problem sys staka da se dobavi tozi red ->
    #pragma comment(linker, "/stack:400000000") */
    using namespace std ;
    double q,m,qp,mp,mo,qo ;
    int *a,*b,*c,*arrayTwo,*prav,*obraten,*array Three,*arrayFour ;
    clock_t qn,qk,mk,mn,qnp,qkp,mkp,mnp,mko,mno,qno, qko ;
    int y,low,high,i,masiv;

    void mergeSort(int numbers[], int temp[], int array_size);
    void m_sort(int numbers[], int temp[], int left, int right);
    void merge(int numbers[], int temp[], int left, int mid, int right);
    void quicksort(int arr[], int low, int high);

    int main() {

    cout<<"Vyvedete broqt na elementite :";
    cin>>masiv; cout <<endl<<endl ;
    a=new int[masiv];
    b=new int[masiv];
    c=new int[masiv];
    arrayTwo= new int[masiv];
    arrayThree= new int[masiv];
    arrayFour= new int[masiv];
    prav=new int[masiv] ;
    obraten=new int[masiv] ;


    for(i=0;i<masiv;i++) {
    a[i]=rand()% masiv + 1;
    b[i]=a[i] ;
    prav[i] =i+1 ;
    obraten[i]=masiv - i ;
    c[i]=masiv -i; }


    qn = clock () ;
    quicksort(a, 0, (masiv - 1));
    qk = clock () ;
    mn = clock () ;
    mergeSort(b, arrayTwo, masiv);
    mk = clock () ;
    q = difftime (qk,qn) ; m = difftime (mk,mn) ;
    q = q / 1000 ; m = m / 1000 ;

    cout <<"Vremeto za sortirane 4rez QuickSort na slu4aino "<<endl ;
    cout <<"generiran masiv e : "<< q <<" sekundi."<<endl<<endl ;
    cout <<"Vremeto za sortirane 4rez MergeSort na slu4aino "<<endl;
    cout <<"generiran masiv e : "<<m <<" sekundi."<<endl<<endl ;

    qnp = clock () ;
    quicksort(prav, 0, (masiv - 1));
    qkp = clock () ;
    mnp = clock () ;
    mergeSort(prav, arrayThree, masiv);
    mkp = clock () ;
    qp = difftime (qkp,qnp) ; mp= difftime (mkp,mnp) ;
    qp = qp / 1000 ; mp = mp / 1000 ;

    cout <<"Vremeto za sortirane 4rez QuickSort na vyzhodq6to "<<endl ;
    cout <<"podreden masiv e : "<< qp <<" sekundi."<<endl<<endl ;
    cout <<"Vremeto za sortirane 4rez MergeSort na vyzhodq6to "<<endl;
    cout <<"podreden masiv e : "<<mp <<" sekundi."<<endl<<endl ;


    qno = clock () ;
    quicksort(obraten, 0, (masiv - 1));
    qko = clock () ;
    mno = clock () ;
    mergeSort(c, arrayFour, masiv);
    mko = clock () ;
    qo = difftime (qko,qno) ; mo= difftime (mko,mno) ;
    qo = qo / 1000 ; mo = mo / 1000 ;


    cout <<"Vremeto za sortirane 4rez QuickSort na nizhodq6to "<<endl ;
    cout <<"podreden masiv e : "<< qo <<" sekundi."<<endl<<endl ;
    cout <<"Vremeto za sortirane 4rez MergeSort na nizhodq6to "<<endl;
    cout <<"podreden masiv e : "<<mo <<" sekundi."<<endl<<endl ;

    cout <<endl<<endl<<"Vremenata za Slu4aen/Vyzhodq6t/Nizhodq6 masiv"<<endl ;
    cout <<"\t s "<<masiv<<" elementa sa syotvetno : "<<endl<<endl ;
    cout <<endl<<"Za QuickSort : "<<"\t"<<q<<"\t"<<qp<<"\t"<<qo<<endl ;
    cout <<endl<<"Za MergeSort : "<<"\t"<<m<<"\t"<<mp<<"\t"<<mo<<endl<<en dl ;

    system ("pause") ;
    return 0;
    }

    void quicksort(int arr[], int low, int high) {
    int i = low;
    int j = high;
    int y = 0;
    int z = arr[(low + high) / 2];
    do {
    while(arr[i] < z) i++;
    while(arr[j] > z) j--;
    if(i <= j) {
    y = arr[i];
    arr[i] = arr[j];
    arr[j] = y;
    i++;
    j--;
    }
    } while(i <= j);
    if(low < j)
    quicksort(arr, low, j);
    if(i < high)
    quicksort(arr, i, high);
    }

    void mergeSort(int numbers[], int temp[], int array_size){

    m_sort(numbers, temp, 0, array_size - 1);
    }

    void m_sort(int numbers[], int temp[], int left, int right){

    int mid;
    if (right > left){

    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, (mid+1), right);
    merge(numbers, temp, left, (mid+1), right);
    }}

    void merge(int numbers[], int temp[], int left, int mid, int right){

    int i, left_end, num_elements, tmp_pos;

    left_end = (mid - 1);
    tmp_pos = left;
    num_elements = (right - left + 1);

    while ((left <= left_end) && (mid <= right))
    {
    if (numbers[left] <= numbers[mid])
    {
    temp[tmp_pos] = numbers[left];
    tmp_pos += 1;
    left += 1;
    }
    else
    {
    temp[tmp_pos] = numbers[mid];
    tmp_pos += 1;
    mid += 1;
    }
    }

    while (left <= left_end)
    {
    temp[tmp_pos] = numbers[left];
    left += 1;
    tmp_pos += 1;
    }
    while (mid <= right)
    {
    temp[tmp_pos] = numbers[mid];
    mid += 1;
    tmp_pos += 1;
    }
    for (i=0; i <= num_elements; i++)
    {
    numbers[right] = temp[right];
    right -= 1;
    }
    }
    Last edited by Rain9333; 25th April 2009 at 22:42.
    MSI X570-A PRO, AMD 5800X3D, Noctua NH-D15, Corsair Vengeance LPX 2x8GB-3600, ASUS RTX ROG 3080 Strix White OC, Samsung 980 Pro 1TB NVMe, Corsair RM750, FD Define R5, Dell 32" 4k G3223Q 144Hz + 3xSamsung G5 32" 144hz, SimLab P1-X, Simucube 2 Pro, HE Ultimate, SRB GT3 Wheel

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Copyright © 1999-2011 . .
iskamPC.com | mobility.BG | Bloody's Techblog | | 3D Vision Blog |