Develop a C++ program that will sort a one-dimensional integer array LIST of dim

Question

Develop a C++ program that will sort a one-dimensional integer array LIST of dimension N. You can try using the selection sort algorithm (simple to write but slow), or the bubble sort algorithm (a little more complex, but faster). In testing your program, it is interesting to note the change in behavior of the sort function (number of iterations) when you change the way your data is organized. Try arranging the data so that it is "completely" out of order, and then try the sort on a list that is almost sorted (i.e. only one or two elements are out of order). Note the number of iterations in each case for the different sort algorithms. Can you develop (or find) an even faster algorithm than selection or bubble?

Explanation / Answer

c++ code for selection sort

#include <iostream>
using namespace std;

//function to sort the array using selection sort
void selectionSort (int arr[], int n)
{
int min;
for (int i = 0; i < n-1; ++i)
{
min = i;
for (int j = i + 1; j <n; ++j)
{
if (arr[j] < arr[min])
{
min = j;
}
}
   swap (arr[i], arr[min]);
}  
}

//function to print the array
void printArrayElements(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << arr[i] << " ";
}
cout << endl;
}

int main ()
{
int arr[] = {10, 2, 45, 18, 16, 30, 29, 1, 1, 100};
int len = (sizeof(arr)/sizeof(*arr)) ;
cout << "Array before sorting : ";
printArrayElements(arr, len);
selectionSort(arr, len);
cout << "Array after sorting : ";
printArrayElements(arr, len);
return 0;
}

better way to sort the array is using quick sort since the time complexity of quick sort is o(nlogn) and for selection sort it is o(n2)

code for quick sort

#include <iostream>

using namespace std;

int partition(int arr[],int start,int end)
{
int v,k,j,temp;
v=arr[start];
k=start;
j=end+1;
do
{
do
k++;
  
while(arr[k]<v&&k<=end);
  
do
j--;
while(v<arr[j]);
  
if(k<j)
{
temp=arr[k];
arr[k]=arr[j];
arr[j]=temp;
}
}while(k<j);
  
arr[start]=arr[j];
arr[j]=v;
return(j);
}

void quickSort(int arr[],int start,int end)
{
int mid;
if(start<end)
{
mid=partition(arr,start,end);
quickSort(arr,start,mid-1);
quickSort(arr,mid+1,end);
}
}

int main()
{
int i;
int arr[] = {10, 2, 45, 18, 16, 30, 29, 1, 1, 100};
int len = (sizeof(arr)/sizeof(*arr)) ;
cout<<"Array before sorting "<<endl;
for(i=0;i<len;i++)
cout<<arr[i]<<" ";
cout<<" ";
quickSort(arr,0,len-1);
cout<<" Array after sorting:"<<endl;
for(i=0;i<len;i++)
cout<<arr[i]<<" ";
cout<<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.