Как найти сортировку отрицательных элементов массива

Improve Article

Save Article

Like Article

Given an array arr[] of N integers, the task is to sort the array without changing the position of negative numbers (if any) i.e. the negative numbers need not be sorted.

Examples: 

Input: arr[] = {2, -6, -3, 8, 4, 1} 
Output: 1 -6 -3 2 4 8
Input: arr[] = {-2, -6, -3, -8, 4, 1} 
Output: -2 -6 -3 -8 1 4 

Approach: Store all the non-negative elements of the array in another vector and sort this vector. Now, replace all the non-negative values in the original array with these sorted values.

Below is the implementation of the above approach:  

Time Complexity: O(n * log n) // sorting an array takes n logn time and traversing the array takes linear time, hence the overall complexity turns out to be O(n * log n)

Auxiliary Space: O(n) // since an extra array is used so the solution takes space equal to the length of the array

Last Updated :
08 Aug, 2022

Like Article

Save Article

На занятии объясняется, как работать с одномерными массивами в Паскале, как использовать генератор случайных чисел — функцию random в Паскале. Рассматривается пример того, как вывести числа Фибоначчи

Материалы сайта labs-org.ru направлены на практическое освоение языка программирования Pascal. Краткие теоретические сведения не претендуют на полное освещение материала по теме; необходимую информацию можно найти в сети Интернет в большом количестве. В наши же задачи входит предоставление возможности получения практических навыков программирования на Паскале. Решенные наглядные примеры и задания изложены по мере увеличения их сложности, что позволит с легкостью изучить материал с нуля.

Одномерные массивы в Паскале

Объявление массива

Массивы в Паскале используются двух типов: одномерные и двумерные.
Определение одномерного массива в Паскале звучит так: одномерный массив — это определенное количество элементов, относящихся к одному и тому же типу данных, которые имеют одно имя, и каждый элемент имеет свой индекс — порядковый номер.
Описание массива в Паскале (объявление) и обращение к его элементам происходит следующим образом:

var dlina: array [1..3] of integer;
begin
dlina[1]:=500; 
dlina[2]:=400; 
dlina[3]:=150;
...

Объявить размер можно через константу:

Инициализация массива

Кроме того, массив может быть сам константным, т.е. все его элементы в программе заранее определены. Описание такого массива выглядит следующим образом:

const a:array[1..4] of integer = (1, 3, 2, 5);

Заполнение последовательными числами:

Результат:
A[1] = 8, A[2] = 9, A[3] = 10, ..., A[N] = A[N-1] + 1

Ввод с клавиатуры:

Пример: Рассмотрим, как происходит ввод массива в Паскале:

writeln ('введите кол-во элементов: ');
readln(n); {если кол-во заранее не известно, - запрашиваем его}
for i := 1 to n do begin
   write('a[', i, ']=');
   read(a[i]);
   ...
end;
...

✍ Пример результата:

введите кол-во элементов: 
3
a[1]=5
a[2]=7
a[3]=4

Вывод элементов массива

Пример: Рассмотрим, как вывести массив в Паскале:

1
2
3
4
5
6
7
8
9
10
11
12
13

var
  a: array[1..5] of integer; {массив из пяти элементов}
  i: integer;
begin
a[1]:=2;
a[2]:=4;
a[3]:=8;
a[4]:=6;
a[5]:=3;
writeln('Массив A:');
for i := 1 to 5 do
    write(a[i]:2); {вывод элементов массива}
end.

✍ Пример результата:

Для работы с массивами чаще всего используется в Паскале цикл for с параметром, так как обычно известно, сколько элементов в массиве, и можно использовать счетчик цикла в качестве индексов элементов.

введите элемент массива: 3.0
введите элемент массива: 0.8
введите элемент массива: 0.56
введите элемент массива: 4.3
введите элемент массива: 23.8
введите элемент массива: 0.7
Массив =  3, 0.8, 0.56, 4.3, 23.8, 0.7

В данном примере работы с одномерным массивом есть явное неудобство: присваивание значений элементам.

Обработка массивов в Паскале, так же как и заполнение массива, происходит обычно с использованием цикла for.

Динамические массивы (pascalAbc.Net)

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

Объявление:

var a: array of integer;
var n:=readInteger;
a:=new integer[n]; // инициализация, выделение памяти для элементов массива

или:

var a: array of integer;
var n:=readInteger;
SetLength(a,n); // устанавливаем размер

Аналогичным образом массивы могут описываться в качестве параметров подпрограмм, например:

procedure p(a: array of integer);

Созданные элементы сразу получают начальное значение, равное нулевому значению соответствующего типа: для чисел это целый или вещественный нуль, для символов — символ с кодом 0, для строк и других ссылочных типов данных — нулевая ссылка nil

Объявление и инициализация массива:

Пример:

begin
  var a: array of integer;
  a := new integer[3];
  a[0] := 5;
  a[1] := 2;
  a[2] := 3;
end.

или в одну строку:

begin
  var a: array of integer;
  a := new integer[3](5,2,3);
  print(a)
end.

или короткая запись:

var a:=Arr(1,2,3);// по правой части - integer

Элементы динамического массива всегда индексируются от 0.

Ввод элементов:

Пример:

var a:=ReadArrInteger(5); // ввод пяти целых
var a:=ReadArrReal(5); // ввод пяти вещественных

Функции генерации массивов:

1. ArrFill :

var a := ArrFill(10, 1); // массив из 10 целых чисел, равных 1

2. ArrGen :

var a := ArrGen(ReadInteger, 1, e -> e + 2); // массив, состоящий из n первых положительных нечетных чисел
a.Print;

Проход по элементам массива:

Пример:

for var i:=0 to a.Length-1 do
  a[i] += 1;

или:

for var i := 0 to a.High do
  a[i] += 1;

Проход по элементам (только для чтения):
Пример:

foreach var x in a do
  Print(x)

Простой вывод элементов:

Writeln(a); // пример вывода: [1,5,3,13,20]

или метод массива Print:

a.Print; // пример вывода: 1 5 3 13 20
a.PrintLines; // каждый элемент с новой строки

Функция Random в Pascal

Для того чтобы постоянно не запрашивать значения элементов массива используется генератор случайных чисел в Паскаль, который реализуется функцией Random. На самом деле генерируются псевдослучайные числа, но суть не в этом.

Для генерации чисел от 0 до n (не включая само значение n, целые числа в интервале [0,N)) используется запись random (n).
Перед использованием функции необходимо инициализировать датчик случайных чисел с помощью процедуры randomize.

Диапазон в Паскале тех самых случайных чисел от a до b задается формулой:

Пример: Заполнение массива случайными числами в Pascal:

1
2
3
4
5
6
7
8
9
10

var f: array[1..10] of integer;
    i:integer;
begin
randomize;
for i:=1 to 10 do
  begin
   f[i]:=random(10); { интервал [0,9] }   
   write(f[i],' ');
  end;
end.

✍ Пример результата: 

Для вещественных чисел в интервале [0,1):

var x: real;
...
x := random(0.0,1.0);;         { интервал [0,1), т.е. единица не включена }

var (a, b, c) := Random3(10.0, 20.0); // диапазон [10, 20)
write(a:0:2,' ',b:0:2,' ', c:0:2) // 14.73 18.63 19.72

var a:=arrRandomInteger(10);

var a:=arrRandomInteger(10,5,15);

Массив =  0.22 0.00 -0.69 -0.35 -0.11 

Числа Фибоначчи в Паскале

Наиболее распространенным примером работы с массивом является вывод ряда чисел Фибоначчи в Паскаль. Рассмотрим его.

Пример: Ряд чисел Фибоначчи: 1 1 2 3 5 8 13…

f[0]:=1;   
f[1]:=1; 
f[2]:=2;  
…

или

f[2]:=f[0]+f[1];
f[3]:=f[1]+f[2];

или

Получили формулу элементов ряда.

Пример: Вычислить и распечатать первые 20 чисел Фибоначчи.

1
2
3
4
5
6
7
8
9
10
11

var i:integer;
f:array[0..19]of integer;
begin
f[0]:=1;
f[1]:=1;
for i:=2 to 19 do
begin
  f[i]:=f[i-1]+f[i-2];
  writeln(f[i])
end;
end.

На данном примере, становится понятен принцип работы с числовыми рядами. Обычно, для вывода числового ряда находится формула определения каждого элемента данного ряда. Так, в случае с числами Фибоначчи, эта формула-правило выглядит как f[i]:=f[i-1]+f[i-2]. Поэтому ее необходимо использовать в цикле for при формировании элементов массива.

Массив =  2 0 4 29 3 11 26 11 9 4 
mas[1] + mas[2] + mas[3] = 6
mas[2] + mas[3] + mas[4] = 33
mas[3] + mas[4] + mas[5] = 36
mas[4] + mas[5] + mas[6] = 43
mas[5] + mas[6] + mas[7] = 40
mas[6] + mas[7] + mas[8] = 48
mas[7] + mas[8] + mas[9] = 46
mas[8] + mas[9] + mas[10] = 24

Задача Array 3. Написать программу решения задачи о печати ряда чисел 2 4 8 16 32 ... 512; для заполнения массива использовать цикл Repeat
[Название файла: taskArray3.pas]

Максимальный (минимальный) элемент массива

Псевдокод:

Поиск максимального элемента по его индексу:

  // …
  var (min, minind) := (a[0], 0);  
  for var i:=1 to a.Length-1 do
    if a[i]<min then
      (min, minind) := (a[i], i);  Result := (min, minind);

  // …
  var (min, minind) := (real.MaxValue, 0);  
  for var i:=0 to a.Length-1 do
    if a[i]<min then
      (min, minind) := (a[i], i);  Result := (min, minind);

begin
  var a := new integer[5];
  a := arrRandomInteger(5); // [86,37,41,45,76] 
  print(a.Min,a.IndexMin); // 37  1
end.

9 5 4 22 23 7 3 16 16 8 
Минимальный элемент массива A[7]=3

3 4 6 -1 6 -2 1 5 0 1 
Количество отрицательных элементов: 2

3  2  6  1  3  4  7  2  >>>  min=1, max=7, distance=3

N=4
mas: 8 9 2 5
>>> 2 8 количество= 2

Исходный массив:
4   -5   10  -10  5
максимальные A[3]=10, A[5]=5

Поиск в массиве

Рассмотрим сложный пример работы с одномерными массивами:

Пример: Дан массив из 10 чисел. Определить, есть ли в массиве число, введенное пользователем. Если есть – выводить «найдено», если нет – «не найдено».
Сложность задания заключается в том, что выводить слова «найдено» или «не найдено» необходимо один раз.

Для решения поставленной задачи понадобится оператор break — выход из цикла.
Решение Вариант 1. Цикл for:

begin
  var a := new integer[10];
  a := arrRandomInteger(5,0,5); //[1,3,5,4,5] 
  print(a.IndexOf(3)) // 1
end.

begin
  var a := new integer[10];
  a := arrRandomInteger(5,0,5); //[1,3,5,4,5] 
  print(a.Contains(3)); // True
  print(3 in a)// True
end.

Рассмотрим эффективное решение:

Задача: найти в массиве элемент, равный X, или установить, что его нет.

Алгоритм:

• начать с 1-го элемента (i:=1);
• если очередной элемент (A[i]) равен X, то закончить поиск иначе перейти к следующему элементу.

решение на Паскале Вариант 2. Цикл While:

Предлагаем посмотреть подробный видео разбор поиска элемента в массиве (эффективный алгоритм):

	 Исходный массив:
	 4  0  1  2  0  1  3  4  1  0
	 Что ищем? 0
	 A[2], A[5], A[10]

Циклический сдвиг

Пример: сдвинуть элементы массива влево на 1 позицию, первый элемент становится на место последнего.

Решение:

  // …
  var v := a[0];
  for var i:=0 to a.Length-2 do
    a[i] := a[i+1];
  a[a.Length-1] := v;

  // …
  var v := a[a.Length-1];
  for var i:=a.Length-1 downto 1 do
    a[i] := a[i-1];
  a[0] := v;

Исходный массив:
  4  -5   3  10  -4  -6   8 -10  1  0
Результат:
  4   3  10  -4  -6   8 -10   1  0 -5

Перестановка элементов в массиве

Рассмотрим, как происходит перестановка или реверс массива.

Пример: переставить элементы массива в обратном порядке

Решение:

begin
var a: array of integer := (1,3,5,7); 
var n := a.Length;
for var i:=0 to n div 2 - 1 do
    Swap(a[i],a[n-i-1]);
End.

begin
var a:=new integer[10];
a:=arrRandomInteger(10);
print(a);// [41,81,84,63,12,26,88,25,36,72] 
Reverse(a);
print(a) //[72,36,25,88,26,12,63,84,81,41] 
end.

 Исходный массив:
-5  3   10  -4  -6   8 -10  1   0  4
 Результат:
0  1  -10   8  -6  -4  10  3  -5  4

Выбор элементов и сохранение в другой массив

Пример: найти в массиве элементы, удовлетворяющие некоторому условию (например, отрицательные), и скопировать их в другой массив

Решение:

writeln('Выбранные элементы');
for i:=1 to count-1 do
   write(B[i], ' ')

// ...
for var i := 0 to a.length - 1 do 
    if a[i] < 0 then
    begin
      b[j] := a[i];
      j += 1;
    end;
  SetLength(b, j);

	 Исходный массив:
	 40   57   30  71  84
	 Заканчиваются на 0:
	 40 30

Сортировка элементов массива

Сортировка методом «Пузырька»

• В таком типе сортировок массив представляется в виде воды, маленькие элементы — пузырьки в воде, которые всплывают наверх (самые легкие).
• При первой итерации цикла элементы массива попарно сравниваются между собой:предпоследний с последним, пред предпоследний с предпоследним и т.д. Если предшествующий элемент оказывается больше последующего, то производится их обмен.
• При второй итерации цикла нет надобности сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте, он самый большой. Значит, число сравнений будет на одно меньше. То же самое касается каждой последующей итерации.

1
2
3
4
5
6
7
8

for i:=1 to N-1 do begin
   for j:=N-1 downto i do
     if A[j] > A[j+1] then begin
       с := A[j];
       A[j] := A[j+1];
       A[j+1] := с;
     end;
 end;

1
2
3
4

for var i := 0 to arr.High - 1 do
    for var j := arr.High - 1 downto i do
      if arr[j] > arr[j + 1] then 
        Swap(arr[j], arr[j + 1]);

Пример:
Исходный массив:
14  25  13  30  76  58  32  11  41  97
Результат:
13  14  25  30  76  97  58  41  32  11

Сортировка методом выбора

• в массиве ищется минимальный элемент и ставится на первое место (меняется местами с A[1]);
• среди оставшихся элементов также производится поиск минимального, который ставится на второе место (меняется местами с A[2]) и т.д.

1
2
3
4
5
6
7
8
9
10

for i := 1 to N-1 do begin
  min:= i ;
  for j:= i+1 to N do
    if A[j] < A[min] then min:=j; 
  if min <> i then begin
    c:=A[i]; 
    A[i]:=A[min]; 
    A[min]:=c;
  end;
end;

1
2
3
4
5
6
7
8

for var i := 0 to a.High-1 do
  begin
    var (min,imin) := (a[i],i);
    for var j := i + 1 to a.High do
      if a[j] < min then
        (min,imin) := (a[j],j);
    Swap(a[imin],a[i]);
  end;

Пример:
Исходный массив:
14  25  13  12  76  58  21  87  10  98
Результат:
10  21  12  13  14  25  76  58  87  98  

Sort(a);
SortByDescending(a);

Быстрая сортировка или quick sort

Алгоритм:

1. Выбирается и запоминается средний элемент массива (присвоим X):



2. Инициализируем две переменные (будущие индексы массива): L:=1, R:=N (N — количество элементов).
3. Увеличиваем L и ищем первый элемент A[L], который больше либо равен X (в итоге он должен находиться справа).
4. Уменьшаем R и ищем элемент A[R], который меньше либо равен X (в итоге он должен находиться слева).
5. Смотрим, если L<=R, то меняем местами A[L] и A[R], возвращаемся к пункту 3.

Выполнение на Паскале:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

procedure QSort ( first, last: integer);
var L, R, c, X: integer;
begin
  if first < last then begin
    X:= A[(first + last) div 2];
    L:= first; R:= last;
 while L <= R do begin
   while A[L] < X do L:= L + 1;
   while A[R] > X do R:= R - 1;
   if L <= R then begin
     c:= A[L]; A[L]:= A[R]; A[R]:= c;
     L:= L + 1; R:= R - 1;
   end;
 end;
  QSort(first, R);   QSort(L, last);
  end;
end.