Сортировка массива

[novopashinmm]

Нужно отсортировать массив по возрастанию сравнивая поочередно соседние члены, причем каждый из элементов массива за один проход цикла может сделать не больше одного перемещения вправо или влево. То есть нужно сравнивать парами 0-й элемент и 1-й, 2-й и 3-й ну и т.д.
Какие Ваши предложения?

Если во 2 цикле j будет принимать значения 0 и 1 поочередно то массив отсортируется.

#include <stdio.h>
main () {
int dig[4]={4,3,2,1};
int i,j,min,d,N;
N=4;
for (i=0; i<N; i++){
for (j=i; j<N; j+=2)
d=j+1;
if dig[d]<dig[j]
min=d;
dig[d]=dig[j];
dig[j]=dig[min];
}
for (i=0; i<N; i++)
printf ("%d", dig[i]);
}

[ViktorR]

Моё предложение:
1. Так думаю, что нужно использовать другой тип цикла:
do
...
while <условие>;
2. При просмотре пар (начинаем с 0-го элемента) фиксируем, было ли перемещение в паре, если да, то переходим к следующей паре (индекс меняем с шагом 2), а иначе индекс меняем с шагом 1.
3. При следующем просмотре начинаем с элемента 1.
Надо учитывать, что для последнего элемента может не быть пары.
4. Цикл завершаем, если перемещений при просмотре не было.
Пример:
3 7 9 5 6
7 3 9 6 5
7 9 3 6 5
9 7 6 3 5
9 7 6 5 3

Вроде так, ...

[novopashinmm]

тут дело в том что, за один проход цикла если это цикл for, каждый элемент может переместится один раз, то есть из 4 3 2 1 подчеркнутые меняются, за один проход цикла можем получить 3 4 1 2. В Вашем алгоритме разве это условие соблюдается? Например 3 за весь этот цикл do ... while, поменяла свое положение 5 раз.

[Serge_Bliznykov]

причем каждый из элементов массива за один проход цикла может сделать не больше одного перемещения вправо или влево.

novopashinmm, мне интересно, а почему перемещение вправо/влево вы понимаете как перемещение вправо влево на соседнюю позицию?!
например, дано 4 3 2 1
меняем 4-ку и 1цу местами
получаем 1 3 2 4
поясните, сколько, по вашему, перемещений в данном примере сделал каждый из элементов массива?

[ViktorR]

В Вашем алгоритме разве это условие соблюдается? Например 3 за весь этот цикл do ... while, поменяла свое положение 5 раз.

1. Не 5, а только 4-е.
2. Да. Алгоритм изложил не точно.
Внутри цикла do ... While должен быть цикл для просмотра всех пар массива (пункт 2).

Serge_Bliznykov

а почему перемещение вправо/влево вы понимаете как перемещение вправо влево на соседнюю позицию?!

Там по условию:

Нужно отсортировать массив по возрастанию сравнивая поочередно соседние члены

Как-то так, ...

[Serge_Bliznykov]

Нужно отсортировать массив по возрастанию сравнивая поочередно соседние члены

так. стоп. ну, сравнивая соседние члены легко найти индекс масимального элемента. Кто помешает потом поменять местами НЕ СОСЕДНИЕ члены массива (ограничения на такой обмен я в условии не увидел. Проглядел?..)

[Helloween]

Предлагаю вашему вниманию новейщий алгоритм сортировки.

#include "stdio.h"
#include "stdlib.h"

void fill(int* arr,const int size)
{
  long seed = time(NULL);
  srand(seed);
  for(int i = 0; i < size; i++)
  {
	 arr[i] = rand()%100 + 1;
  }
}

bool sorted(int* arr,const int size)
{
  for(int i = 0; i < size - 1; i++)
	 if(arr[i+1] < arr[i])
	   return false;
  return true;
}

int main()
{
  int arr[4] = {0,};
  fill(arr,4);
  while(!sorted(arr,4))
	fill(arr,4);
  for(int i = 0; i < 4; i++)
	printf("%d ",arr[i]);
  return 0;
}

[ViktorR]

Прошу простить за делитанский подход, но используя пример выше
реализовал алгоритм так:

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include <time.h>

void fill(int* arr,const int size)
{
  long seed = time(NULL);
  srand(seed);
  for(int i = 0; i < size; i++)
  {
	 arr[i] = rand()%100 + 1;
  }
};

bool sorted(int* arr,const int size)
{
	bool chng;
   int i, tmp;
   chng = false;
   i = 0;
   do
  {
     if (arr[i] < arr[i+1])
     {
        tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
        chng = true;
        i = i + 2;
     }
     else
        i = i + 1;
  } while (i <= (size -1));
return chng;
};

int main()
{
  const int n = 10;
  int arr[n] = {0,};
  fill(arr,n);
  do
  {
    for(int i = 0; i < n; i++)
	   printf("%d ",arr[i]);
       printf("\n");
  } while(sorted(arr,n));

  for(int i = 0; i < n; i++)
	printf("%d ",arr[i]);
  return 0;
}

Проверить верность записи на Си и его работу пока не могу.
Проверил и отладил.

Во вложении этот алгоритм на Паскале.


Как-то так, ...

[novopashinmm]

Сообщение от Serge_Bliznykov

novopashinmm, мне интересно, а почему перемещение вправо/влево вы понимаете как перемещение вправо влево на соседнюю позицию?!
например, дано 4 3 2 1
меняем 4-ку и 1цу местами
получаем 1 3 2 4
поясните, сколько, по вашему, перемещений в данном примере сделал каждый из элементов массива?

Вас понял, точно, перемещение влево, вправо не подразумевает перемещение только на соседнюю позицию, 1 и 4 тоже могут поменяться за один ход цикла. тогда 4 3 2 1 отсортируется за 3 цикла
4 3 2 1
3 4 1 2
2 1 4 3
1 2 3 4