Results 1 to 7 of 7
Thread: Quick & Merge Sort
Hybrid View
-
15th April 2009 21:26 #1
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
-
15th April 2009 22:06 #2
-
15th April 2009 22:21 #3
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
-
16th April 2009 23:32 #4Registered User
Join Date: Dec:2007
Location: Sofia
Posts: 366
1. - ( ).
2. Quick_sort(), Quick_sort() -, -. - , Partition() .
3. pivot . .
-
17th April 2009 15:12 #5MSI 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
-
17th April 2009 21:15 #6Registered User
Join Date: Dec:2007
Location: Sofia
Posts: 366
#pragma comment(linker, "/stack:10000000")
Dev-C++ - , . , - , , - VC++2008, ..
-
17th April 2009 21:32 #7
( , (( ,
, ...)) ). , .
#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




Reply With Quote



Lenovo ThinkPad 15 IdeaPad 15
5th May 2023, 22:16 in