C Сортировка массива целым числом

Question

Итак, мне нужно отсортировать массив целых чисел так, чтобы каждое меньшее число, чем какое-либо число scanf 'd целое, находится слева, эта переменная набора находится посередине, а каждое большее число справа , У меня есть левая и правая часть, но я не уверен, как сделать так, чтобы переменная была в середине .. какие-нибудь идеи?

#include <stdio.h> 
int main() 
{ 
    int y, i, k, temp; 
    printf("give integer\n"); 
    scanf("%d", &y); 
    int x[10] = {5,8,9,4,2,3,2,4,5,6}; 
    i=0; 
    k=1; 
    while(i<10) 
    { 
     while(x[i]>y&&k<10) 
     { 
      temp=x[k]; 
      x[k]=x[i]; 
      x[i]=temp; 
      k++; 
     }  

     i++; 
     k=i+1; 
    } 


    for(i=0; i<10; i++) 
    { 
     printf("x[%d]=%d\n", i, x[i]); 
    } 
} 

Пример ввода/вывода:

input: x[i]={5,2,1,6,7,3,2,4,5,6} y=5 
output: x[i]={2,1,4,3,2,5,5,7,6,6} 

Answer 1

Вы ищете алгоритм, аналогичный «раздела», как и в алгоритме быстрой сортировки. Идея состоит в том, чтобы иметь 2 индекса i и j, где i используется для итерации по массиву, тогда как j является индексом первого элемента, который больше или равен y.

После этого первого цикла у вас есть цифры, которые меньше y слева, а остальные цифры справа. Однако на самом деле вы хотите сгруппировать значения, равные y, и иметь только номер, превышающий y справа. Поэтому я предлагаю сделать то же самое на интервале [j, n], но теперь я тоже двигаюсь, когда он равен.

// Function to exchange the values of 2 integer variables. 
void swap(int *a, int *b) { 
    int buf = *a; 
    *a = *b; 
    *b = buf; 
} 

// Do the job, in place. 
void partition(int *tab, int n, int y) { 
    // This first part will move every values strictly lesser than y on the left. But the right part could be "6 7 5 8" with y=5. On the right side, numbers are greater or equal to `y`. 
    int j = 0; // j is the index of the position of the first item greater or equal to y. 
    int i; 
    for (i = 0; i < n; i++) { 
     if (tab[i] < y) { 
     // We found a number lesser than y, we swap it with the first item that is greater or equal to `y`. 
      swap(&tab[i], &tab[j]); 
      j++; // Now the position of the first value greater or equal to y is the next one. 
     } 
    } 

    // Basically the same idea on the right part of the array. 
    for (i = j; i < n; i++) { 
     if (tab[i] <= y) { 
      swap(&tab[i], &tab[j]); 
      j++; 
     } 
    } 
} 

int main() { 
    int y; 
    printf("give integer\n"); 
    scanf("%d", &y); 
    int x[10] = {5,8,9,4,2,3,2,4,5,6}; 
    partition(x, 10, y); 

    int i; 
    for(i=0; i<10; i++) 
    { 
     printf("x[%d]=%d\n", i, x[i]); 
    } 

    return 0; 
} 

Этот код дает, с x = {5,2,1,6,7,3,2,4,5,6}; и y = 5:

x[0]=2 
x[1]=1 
x[2]=3 
x[3]=2 
x[4]=4 
x[5]=5 
x[6]=5 
x[7]=7 
x[8]=6 
x[9]=6 

Первые 5 элементов ниже, чем 5, а остальные больше или равно 5.

Answer 2

Вместо того чтобы использовать один массив вы можете использовать два массива для снижения сложности кода.

Поиск чисел те менееy, а затем хранить их в массиве. Скажем A[ ]
Опять поиск чисел те большеy, а затем хранить их в другом массиве B[ ]
Как так ..

Теперь у вас есть все из них. Вы можете сохранить их в другом массиве, который можно назвать сортированным массивом. Или если вы просто хотите, чтобы распечатать их, а затем

1. печати все элементы первого массива A[ ]
2. затем распечатать y
3. наконец напечатать элементы второго массива B[ ]

Это все. Надеюсь, эта идея поможет вам быстро скопировать и решить эту проблему.

Answer 3

Это простой, прямой способ сортировки массива x в другой массив y по разделам.Числа сортируются < = раздел на левой стороне, а> раздел на правой:

[EDIT], чтобы проиллюстрировать способ согласно OP осветления:
, если массив имеет 2 элемента, которые равны р, то он должен быть устроен так: xxxxxppyyyy, где xp и p нельзя смешивать с x или y.
Кроме того, что пример: xxxxxppyyyy слишком долго массива, поэтому я предполагаю, что вы имели в виду xxxxppxxxx (10 элементов, а не 11).

int * partitionArr(int *z, int p); 

int main(void) 
{ 
    int i, x[10] = {5,8,9,4,2,3,2,4,5,6}; 
    //int i, x[10] = {3,3,3,3,3,8,8,8,8,8}; 
    int *y; 
    int partition; 

    printf("enter a number from 0 to 10\n"); 
    scanf("%d", &partition); 

    y = malloc(sizeof(int) * sizeof(x)/sizeof(x[0])+1); //+1 for inserting partition 
    y = partitionArr(x, partition); 

    printf("Partition is: %d\n\n", partition); 
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++) 
    { 
     printf("y[%d] == %d\n", i, y[i]); 
    } 
    getchar(); 
    getchar(); 

    return 0; 
} 

int * partitionArr(int *z, int p) 
{ 
    int i=0,j=0; 
    int x[10]; 

    //load y with x 
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++) x[i] = z[i]; 

    for(i=0;i<sizeof(x)/sizeof(x[0]);i++) 
    { 
     if(x[i]<p) 
     { 
      z[j] = x[i]; 
      j++; 
     } 
    } 
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++) 
    { 
     if(x[i]==p) 
     { 
      z[j] = x[i]; 
      j++; 
     } 
    } 
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++) 
    { 
     if(x[i]>p) 
     { 
      z[j] = x[i]; 
      j++; 
     } 
    } 
    return z; 
} 

ВЫХОД для следующих условий: х < P; x == P; х < р (единственный способ обеспечить P в середине)

Answer 4

Простой алгоритм, в случае, если вы хотите работать это через себя:

1. разделов весь массив в качестве [min..y][y+1..max], и принять примечание о том, где находится раскол.
2. переразделать первую часть только как [min..y-1][y..y].

Array теперь следует разделить [min..y-1][y..y][y+1..max].

Простейший должен иметь функцию partition_helper, которая выполняет разделение и возвращает позицию разделения. Тогда первичная функция секционирования вызывает эту функцию дважды, с правильными аргументами.

Вы также можете разделить другой путь, [min..y-1][y..max], а затем переразделить последнюю часть как [y..y][y+1..max], конечный результат должен быть таким же.