c-在不修改元素、不使用辅助数组或不使用任何内置函数的情况下，对具有重复值的数组进行排序

Question

因此，正如问题所说，我只是试图对具有重复值的数组进行排序。数组已正确排序，但当向数组提供重复值时会出现问题

O/p：无重复

Enter the size of the array : 5
Enter the 5 elements
7 3 4 8 1
After sorting: 1 3 4 7 8 
Original array value 7 3 4 8 1 

O/p：具有重复

5 3 1 1 4
After sorting: 1 3 4 1 3 
Original array value 5 3 1 1 4 

我知道这是一个特定的练习(作业？(，不可能修改数组而不使用额外的数组。

这意味着经典的排序算法无法工作。

迭代搜索最小值是一个可能的解决方案，即使不是有效的O(n^2(。

为了应对重复，不仅需要记住当前的最小值，还需要记住它的位置。

这是一种可能的实现方式。

#include <stdio.h>
#include <stdlib.h>
void print_sort(int *arr, int size) //function definition
{
int i, j, k, largest = arr[0], smallest = arr[0];
int i_smallest = 0;
for (i = 1; i < size; i++ ) {
if (arr[i] > largest) {
largest = arr[i];
}
if(arr[i] < smallest) {
smallest = arr[i];
i_smallest = i;
}
}
printf("After sorting: ");
for (i = 0; i < size; i++) {
int temp = largest + 1;
int i_temp = -1;
printf("%d ", smallest);
if (i == size-1) break;
for (k = 0; k < size; k++) {
if (arr[k] < smallest) continue;
if (arr[k] == smallest) {
if (k <= i_smallest) continue;
i_temp = k;
temp = smallest;
break;
}
if (arr[k] < temp) {
temp = arr[k];
i_temp = k;
}
}
smallest = temp;
i_smallest = i_temp;
}
printf("n");

printf("Original array value ");
for( i = 0 ; i < size ; i++ )
{
printf("%d ",arr[i]);
}
}
int main(void) {
int size, i;
printf("Enter the size of the array : ");
if (scanf("%d", &size) != 1) exit(1);
int arr[size];
printf("Enter the %d elementsn",size);
for (i = 0; i < size; i++) {
if (scanf("%d", &arr[i]) != 1) exit(1);
}
print_sort(arr, size);
return 0;
}

也许将每个读取值直接插入排序后的数组更容易。因此，您不必在之后对数组进行排序。如果你想这样做的话，geeksfoeks.org也有我已经使用过的C的好例子(https://www.geeksforgeeks.org/search-insert-and-delete-in-a-sorted-array/)。

// C program to implement insert operation in
// an sorted array.
#include <stdio.h>
// Inserts a key in arr[] of given capacity. n is current
// size of arr[]. This function returns n+1 if insertion
// is successful, else n.
int insertSorted(int arr[], int n, int key, int capacity)
{
// Cannot insert more elements if n is already
// more than or equal to capacity
if (n >= capacity)
return n;
int i;
for (i = n - 1; (i >= 0 && arr[i] > key); i--)
arr[i + 1] = arr[i];
arr[i + 1] = key;
return (n + 1);
}
/* Driver program to test above function */
int main()
{
int arr[20] = { 12, 16, 20, 40, 50, 70 };
int capacity = sizeof(arr) / sizeof(arr[0]);
int n = 6;
int i, key = 26;
printf("nBefore Insertion: ");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
// Inserting key
n = insertSorted(arr, n, key, capacity);
printf("nAfter Insertion: ");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}