Given an array A of objects with key values, we can do the following two stepts
ID: 3856184 • Letter: G
Question
Given an array A of objects with key values, we can do the following two stepts to make all comparison-based sorting algoritms stable while sorting this array.
-Reconstruct the array A with new objects having another index field, where A[i].key = A[i].key and A[i].orginal-index = i, i;
-Write a method compare(A[i], A[j]) to make all comparison-based sorting algorithms stable. That is, while comparing two elements A[i] and A[j], we use compare(A[i], A[j]) rather than using comparison operators (=,>,<, or ).
compare(A[i], A[j]) //pre-cond: i != j
//return 1 if A[i] should appear after A[j] in the sorted order
//return -1 otherwise
My answer was:
if(A[i] > A[j]){
return 1;
}esle{
return -1;
}
But apparently thats incorrect....
Explanation / Answer
Hi, what I understand from the problem posted here is that, we need to have one function compare which will be used in place of <,>,= etc. I am using very simple sorting example here in C++. for demonstrating this. Please let me know if my understanding is correct. If I am wrong please comment on the answer, I'll definitely improve it.
Please note that I am considering assumption that only numeric array will be sorted with my method. I am not making it generic as it is not mentioned in the question
Below is your program: -
#include<iostream>
using namespace std;
int compare(int a,int b) {
if(a > b) {
return 1;
} else {
return -1;
}
}
void insertion_sort (int arr[], int length){
int j, temp;
for (int i = 0; i < length; i++){
j = i;
while (j > 0 && compare(arr[j-1],arr[j]) == 1 ){ //arr[j-1] > arr[j] was here previously
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}
}
}
int main(){
int A[] = {12, 11, 13, 5, 6};
int n = sizeof(A)/sizeof(A[0]);
cout<<"Before sorting: ";
for(int i = 0; i < n;i ++) {
cout<<A[i]<<" ";
}
insertion_sort(A,n);
cout<<" After sorting: ";
for(int i = 0; i < n;i ++) {
cout<<A[i]<<" ";
}
return 0;
}
Sample run: -
Before sorting: 12 11 13 5 6
After sorting: 5 6 11 12 13
--------------------------------
Process exited after 0.2274 seconds with return value 0
Press any key to continue . . .
Please do comment me if my understanding of this question is wrong I'll love to help
UPDATE
Java code: -
package time;
public class Compare {
static int compare(int a, int b) {
if (a > b) {
return 1;
} else if (a == b) {
return -1; // for === part , we need to check the indexes and here b
// is having larger index than a as we are passing it in
// that way. So returning -1
} else {
return -1;
}
}
static void insertion_sort(int arr[], int length) {
int j, temp;
for (int i = 0; i < length; i++) {
j = i;
while (j > 0 && compare(arr[j - 1], arr[j]) == 1) { // arr[j-1] >
// arr[j] was
// here
// previously
temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
j--;
}
}
}
public static void main(String args[]) {
int A[] = { 12, 11, 13, 5, 6 };
int n = A.length;
System.out.print("Before sorting: ");
for (int i = 0; i < n; i++) {
System.out.print(A[i] + " ");
}
insertion_sort(A, n);
System.out.print(" After sorting: ");
for (int i = 0; i < n; i++) {
System.out.print(A[i] + " ");
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.