Merge Sort
#include<iostream>
using namespace std;
int temp[1000];
void merge(int a[],int startIndex,int endIndex){
int mid=(startIndex+endIndex)/2;
int i,j,k;
i=startIndex;j=mid+1;k=0;
while(i<=mid&&j<=endIndex){
if(a[i]<a[j]){
temp[k]=a[i]; i++;k++;
}
else{
temp[k]=a[j]; j++;k++;
}
}
while(i<=mid){
temp[k]=a[i]; i++;k++;
}
while(j<=endIndex){
temp[k]=a[j]; j++;k++;
}
}
void mergesort(int a[],int startIndex,int endIndex){
if(startIndex<endIndex){
int mid=(startIndex + endIndex)/2;
mergesort(a,startIndex,mid);
mergesort(a,mid+1,endIndex);
merge(a,startIndex,endIndex);
}
}
main(){
int arr[100], n;
cin >> n;
for (int i = 0 ; i < n; i++) {
cin >> arr[i];
}
mergesort(arr,0,n-1);
cout <<"\n";
for (int i = 0 ; i < n; i++) {
cout << temp[i]<<"\t";
}
}
quick Sort
#include<iostream>
using namespace std;
int partion(int arr[],int startIndex,int endIndex){
int pindex=startIndex+1;
int pivot=arr[startIndex];
int i;
for(i=startIndex+1;i<=endIndex;i++){
if(pivot>arr[i]){
swap(arr[i],arr[pindex]);
pindex++;
}
}
swap(arr[startIndex],arr[pindex-1]);
return pindex-1;
}
void quicksort(int arr[],int startIndex,int endIndex ){
if(startIndex>=endIndex){
return;
}
int x= partion(arr,startIndex,endIndex);
quicksort(arr,startIndex,x);
quicksort(arr,x+1,endIndex);
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
quicksort(arr,0,n-1);
for(i=0;i<n;i++){
cout<<arr[i]<<"\t";
}
}
Selection Sort
#include<iostream>
using namespace std;
void selectionSort(int arr[],int startIndex, int endIndex){
int temp=arr[0];
for(int i=0;i<=endIndex;i++){
int minIndex=i;
for(int j=i+1;j<=endIndex;j++){
if(arr[minIndex]>arr[j]){
minIndex=j;
}
}
swap(arr[i],arr[minIndex]);
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
selectionSort(arr,0,n-1);
for(i=0;i<n;i++){
cout<<arr[i]<<"\t";
}
}
Insertion Sort
#include<iostream>
using namespace std;
void shift(int arr[],int start,int hole){
int temp;
for(int i=hole;i>start;i--){
arr[i]=arr[i-1];
}
}
void insertionsort(int arr[],int endIndex){
int temp=0;
for(int i=1;i<=endIndex;i++){
int temp=arr[i];
int j=i-1;
while(arr[i]<arr[j]&&j>=0){
j--;
}
if(j==-1){
shift(arr,0,i);
arr[0]=temp;
}
else{
shift(arr,j+1,i);
arr[j+1]=temp;
}
}
}
main(){
int n,arr[1000],i,j,k;
cin>>n; //size of array
for(i=0;i<n;i++){
cin>>arr[i];
}
insertionsort(arr,n-1);
for(i=0;i<n;i++){
cout<<arr[i]<<"\t";
}
}
No comments:
Post a Comment