#include<iostream>
using namespace std;
template<class T>
class Sorting{
T * list;
int n;
void swap(T & x1, T & x2){
T x3 = x1;
x1 = x2;
x2 = x3;
}
public:
Sorting(int x=5){
n=x;
list = new T[n];
}
T * getList(){
T * temp = new T[n];
for(int i=0;i<n;i++)
temp[i] = list[i];
return temp;
}
void inputList(){
for(int i=0;i<n;i++)
cin>>list[i];
}
void display(){
for(int i=0;i<n;i++)
cout<<list[i]<<" ";
}
void selectionSort(){
/***** algorithm ***
1.Find the minimum value in the list
2.Swap it with the value in the first position
3.Repeat the steps above for the remainder of the list
(starting at the second position and advancing each time)
*/
T * temp = getList();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++)
{
if(temp[j]<temp[i]){
swap(temp[i], temp[j]);
}
}
}
cout<<"After applying \"selection\" sort, the list become:\n";
for(int i=0;i<n;i++)
cout<<temp[i]<<" , ";
}
void insertionSort(){
/***** algorithm ***
1. current position begin with 0
2. increment current position
3. insert current value (position i) in appropiate position of the left list
4. repeat step 2
*/
T * temp = getList();
for(int i=0;i<n-1;i++){ //i<n-1 because j= i+1, last value of j is the last element
int j=i+1;
while(temp[j]<temp[j-1] && j>0){ //swap current position with previous one if it is less
swap(temp[j], temp[j-1]);
j--; // decrement current position
}
}
cout<<"After applying \"insertion\" sort, the list become:\n";
for(int i=0;i<n;i++)
cout<<temp[i]<<" , ";
}
void shellSort(){
/***** algorithm ***
1. calculate Shell's increment, begin with n/2
2. for position i [0:increment]
sort the list using insertion sort start with i, with increment=increment
3. set increment = increment/2, repeat step 2 until increment = 1
*/
T * temp = getList();
int increment = n/2;
while(increment >= 1){
for(int i=0; i<increment; i++){
/////////insertion sort that start from i with increment = increment
for(int j=i;j<n-increment;j+=increment){
int k = j+increment;
while(temp[k]<temp[k-increment] && k>i){
swap(temp[k],temp[k-increment]);
k-=increment;
}
}
/////////////////////////////////////////////////
}
increment /=2;
}
cout<<"After applying \"shell\" sort, the list become:\n";
for(int i=0;i<n;i++)
cout<<temp[i]<<" , ";
}
void quickSort(T * temp, int l,int h){
/***** algorithm ***
1. Pick a pivot from the list.
2. Do partition operation by reordering the list so that:
- all elements with values less than the pivot come before the pivot,
- while all elements with values greater than the pivot come after it
(equal values can go either way).
After this partitioning, the pivot is in its final position.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
*/
int i=l,j=h;
int m=(l+h)/2;
T pivot=temp[m];
while(i<=j){ //partition
while(temp[i]<pivot)
i++;
while(temp[j]>pivot)
j--;
if(i<=j){
swap(temp[i],temp[j]);
i++;
j--;
}
}
if(l<j)
quickSort(temp,l,j);
if(h>i)
quickSort(temp,i,h);
}
void mergeSort(T * temp, int l, int h){
/*
1. split list recursively
2. call merge function to merge splited list in order
*/
if(l < h){
int m = (l+h)/2;
mergeSort(temp,l,m);
mergeSort(temp,m+1,h);
merge(temp,l,m,h);
}
}
private:
void merge(T * temp, int l, int m, int h){ //function for merge sort312
T * aux = new T[m];
int i=l,j=l,k=l;
//copy first half list temp to auxilary array aux
while(j<=m)
aux[j++] = temp[i++];
//merge aux with second half temp into temp
i=l,j=m+1;
while(i<=j && j<=h){ //i<j alway true therfore all second half will be copied "<="
if(aux[i]<temp[j] && i<=m) //i<=m (because i=m first half ends
temp[k++] = aux[i++];
else
temp[k++] = temp[j++];
}
//copy remaining first half if any
while(k<=h)
temp[k++] = aux[i++];
}
};
void main()
{
int ch,size;
cout<<"\nWhat is the size of the list?\n";
cin>>size;
Sorting<int> st(size);
cout<<"\nPlease insert list:\n";
st.inputList();
do{
cout<<"\nPlease select your choice:\
\n 1.apply insertion sort\
\n 2.apply selection sort\
\n 3.apply shell sort\
\n 4.apply quick sort\
\n 5.apply merge sort\
\n 6.display original list\
\n 7.input another list\n";
cin>>ch;
switch(ch){
case 1:
st.insertionSort();
break;
case 2:
st.selectionSort();
break;
case 3:
st.shellSort();
break;
case 4:
{
int * temp = st.getList();
st.quickSort(temp,0,size-1);
cout<<"After applying \"quick\" sort, the list become:\n";
for(int i=0;i<size;i++)
cout<<temp[i]<<" , ";
}
break;
case 5:
{
int * temp = st.getList();
st.mergeSort(temp,0,size-1);
cout<<"After applying \"merge\" sort, the list become:\n";
for(int i=0;i<size;i++)
cout<<temp[i]<<" , ";
}
break;
case 6: st.display();
break;
case 7:
cout<<"\nPlease insert list:\n";
st.inputList();
break;
}
}while(ch);
}#include<iostream>
using namespace std;
template<class T>
class Sorting{
T * list;
int n;
void swap(T & x1, T & x2){
T x3 = x1;
x1 = x2;
x2 = x3;
}
public:
Sorting(int x=5){
n=x;
list = new T[n];
}
T * getList(){
T * temp = new T[n];
for(int i=0;i<n;i++)
temp[i] = list[i];
return temp;
}
void inputList(){
for(int i=0;i<n;i++)
cin>>list[i];
}
void display(){
for(int i=0;i<n;i++)
cout<<list[i]<<" ";
}
void selectionSort(){
/***** algorithm ***
1.Find the minimum value in the list
2.Swap it with the value in the first position
3.Repeat the steps above for the remainder of the list
(starting at the second position and advancing each time)
*/
T * temp = getList();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++)
{
if(temp[j]<temp[i]){
swap(temp[i], temp[j]);
}
}
}
cout<<"After applying \"selection\" sort, the list become:\n";
for(int i=0;i<n;i++)
cout<<temp[i]<<" , ";
}
void insertionSort(){
/***** algorithm ***
1. current position begin with 0
2. increment current position
3. insert current value (position i) in appropiate position of the left list
4. repeat step 2
*/
T * temp = getList();
for(int i=0;i<n-1;i++){ //i<n-1 because j= i+1, last value of j is the last element
int j=i+1;
while(temp[j]<temp[j-1] && j>0){ //swap current position with previous one if it is less
swap(temp[j], temp[j-1]);
j--; // decrement current position
}
}
cout<<"After applying \"insertion\" sort, the list become:\n";
for(int i=0;i<n;i++)
cout<<temp[i]<<" , ";
}
void shellSort(){
/***** algorithm ***
1. calculate Shell's increment, begin with n/2
2. for position i [0:increment]
sort the list using insertion sort start with i, with increment=increment
3. set increment = increment/2, repeat step 2 until increment = 1
*/
T * temp = getList();
int increment = n/2;
while(increment >= 1){
for(int i=0; i<increment; i++){
/////////insertion sort that start from i with increment = increment
for(int j=i;j<n-increment;j+=increment){
int k = j+increment;
while(temp[k]<temp[k-increment] && k>i){
swap(temp[k],temp[k-increment]);
k-=increment;
}
}
/////////////////////////////////////////////////
}
increment /=2;
}
cout<<"After applying \"shell\" sort, the list become:\n";
for(int i=0;i<n;i++)
cout<<temp[i]<<" , ";
}
void quickSort(T * temp, int l,int h){
/***** algorithm ***
1. Pick a pivot from the list.
2. Do partition operation by reordering the list so that:
- all elements with values less than the pivot come before the pivot,
- while all elements with values greater than the pivot come after it
(equal values can go either way).
After this partitioning, the pivot is in its final position.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
*/
int i=l,j=h;
int m=(l+h)/2;
T pivot=temp[m];
while(i<=j){ //partition
while(temp[i]<pivot)
i++;
while(temp[j]>pivot)
j--;
if(i<=j){
swap(temp[i],temp[j]);
i++;
j--;
}
}
if(l<j)
quickSort(temp,l,j);
if(h>i)
quickSort(temp,i,h);
}
void mergeSort(T * temp, int l, int h){
/*
1. split list recursively
2. call merge function to merge splited list in order
*/
if(l < h){
int m = (l+h)/2;
mergeSort(temp,l,m);
mergeSort(temp,m+1,h);
merge(temp,l,m,h);
}
}
private:
void merge(T * temp, int l, int m, int h){ //function for merge sort312
T * aux = new T[m];
int i=l,j=l,k=l;
//copy first half list temp to auxilary array aux
while(j<=m)
aux[j++] = temp[i++];
//merge aux with second half temp into temp
i=l,j=m+1;
while(i<=j && j<=h){ //i<j alway true therfore all second half will be copied "<="
if(aux[i]<temp[j] && i<=m) //i<=m (because i=m first half ends
temp[k++] = aux[i++];
else
temp[k++] = temp[j++];
}
//copy remaining first half if any
while(k<=h)
temp[k++] = aux[i++];
}
};
void main()
{
int ch,size;
cout<<"\nWhat is the size of the list?\n";
cin>>size;
Sorting<int> st(size);
cout<<"\nPlease insert list:\n";
st.inputList();
do{
cout<<"\nPlease select your choice:\
\n 1.apply insertion sort\
\n 2.apply selection sort\
\n 3.apply shell sort\
\n 4.apply quick sort\
\n 5.apply merge sort\
\n 6.display original list\
\n 7.input another list\n";
cin>>ch;
switch(ch){
case 1:
st.insertionSort();
break;
case 2:
st.selectionSort();
break;
case 3:
st.shellSort();
break;
case 4:
{
int * temp = st.getList();
st.quickSort(temp,0,size-1);
cout<<"After applying \"quick\" sort, the list become:\n";
for(int i=0;i<size;i++)
cout<<temp[i]<<" , ";
}
break;
case 5:
{
int * temp = st.getList();
st.mergeSort(temp,0,size-1);
cout<<"After applying \"merge\" sort, the list become:\n";
for(int i=0;i<size;i++)
cout<<temp[i]<<" , ";
}
break;
case 6: st.display();
break;
case 7:
cout<<"\nPlease insert list:\n";
st.inputList();
break;
}
}while(ch);
}
0 comments:
Posting Komentar