Lect5 – Указатели и сортировка (1)

1. Указатели

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
1

2. Указатели

<тип> *<идентификатор>;
int *ptr, *ptr1;
float *p, *p1;
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
2

3. Выделение памяти

int *p1, *p2;
p1 = new int;
(*p1) = 10;
p2 = p1;
cout << *p1 << " " << *p2 << endl;
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
3

4. Выделение памяти

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
4

5. Очистка памяти

int *p1 = new int;
(*p1) = 10;
cout << p1 << " " << *p1 << endl;
delete p1;
cout << p1 << " " << *p1 << endl;
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
5

6. Очистка памяти

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
6

7. Динамические массивы

int *x, n;
cin >> n;
x = new int[n];
for(int i=0;i<n;i++) {
cin >> x[i];
}
for(int i=0;i<n;i++) {
cout << x[i] << “ “;
}
delete[]x;
int *x, n;
cin >> n;
x = new int[n];
for(int* p=x;p<(x+n);p++) {
cin >> *p;
}
for(int* p=x;p<(x+n);p++) {
cout << *p << “ “;
}
delete[]x;
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
7

8. Указатели и функции

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
8

9. Передача по значению

void func1(int x){
cout << "Func1 " << x << endl;
x++;
cout << "Func2 " << x << endl;
}
int main(){
int x = 10;
cout << "Main1 " << x << endl;
func1(x);
cout << "Main2 " << x << endl;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
9

10. Передача по указателю

void func1(int *x){
cout << "Func1 " << *x << endl;
(*x)++;
cout << "Func2 " << *x << endl;
}
int main(){
int *x = new int;
*x = 10;
cout << "Main1 " << *x << endl;
func1(x);
cout << "Main2 " << *x << endl;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
10

11. Передача по указателю - удаление

Передача по указателю удаление
void func1(int *x){
cout << "Func1 " << *x << endl;
delete x;
cout << "Func2 " << *x << endl;
}
int main(){
int *x = new int;
*x = 10;
cout << "Main1 " << *x << endl;
func1(x);
cout << "Main2 " << *x << endl;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
11

12. Передача по указателю - создание

Передача по указателю создание
void func1(int *x){
cout << "Func1 " << *x << endl;
x = new int; *x = 20;
cout << "Func2 " << *x << endl;
}
int main(){
int *x = new int;
*x = 10;
cout << "Main1 " << *x << endl;
func1(x);
cout << "Main2 " << *x << endl;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
12

13. Передача массивов

void func1(int *arr){
cout << arr[0] << endl;
}
int main(){
int n;
cin >> n;
int* mas = new int[n];
for(int i=0;i<n;i++){
cin >> mas[i];
}
func1(mas)
};
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
13

14. Функция удвоения элементов массива

int* readArray(int size){
int* arr = new int[size];
for(int i=0;i<size;i++)
cin >> arr[i];
return arr;
}
void printArray(int* arr, int size){
for(int i=0;i<size;i++)
cout << arr[i] << " ";
}
void doubleArray(int* arr, int size){
for(int i=0;i<size;i++)
arr[i]*=2;
}
int main(){
int n;
cin >> n;
//1 2 3 4 5
int* mas = readArray(n);
doubleArray(mas, n);
printArray(mas, n);
cout << endl;
doubleArray(mas, n);
printArray(mas, n);
return 0;
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
14

15. Сортировка пузырьком

void sortArray(int* arr, int size){
bool isSorted = true;
do{
isSorted = true;
for(int i=0;i<size-1;i++)
if(arr[i]>arr[i+1]){
swap(arr[i], arr[i+1]);
isSorted = false;
}
}while(!isSorted);
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
15

16. Сортировка пузырьком

void sortArray(int* arr, int size){
bool isSorted = true;
do{
isSorted = true;
for(int i=0;i<size-1;i++)
if(arr[i]>arr[i+1]){
swap(arr[i], arr[i+1]);
isSorted = false;
}
}while(!isSorted);
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
16

17. Сортировка пузырьком

void sortArray(int* arr, int size){
bool isSorted = true;
do{
isSorted = true;
for(int i=0;i<size-1;i++)
if(arr[i]>arr[i+1]){
swap(arr[i], arr[i+1]);
isSorted = false;
}
}while(!isSorted);
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
17

18. Сортировка пузырьком

void sortArray(int* arr, int size){
bool isSorted = true;
do{
isSorted = true;
for(int i=0;i<size-1;i++)
if(arr[i]>arr[i+1]){
swap(arr[i], arr[i+1]);
isSorted = false;
}
}while(!isSorted);
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
18

19. Сортировка выбором

void sortArray(int* arr, int size){
for(int i=0;i<size-1;i++){
int imin = i;
for(int j=i+1;j<size;j++)
if(arr[j]<arr[imin])
imin = j;
swap(arr[i],arr[imin]);
}
}
bool compare(int a, int b){
return a<b;
}
void sortArray(int* arr, int size){
for(int i=0;i<size-1;i++){
int imin = i;
for(int j=i+1;j<size;j++)
if(compare(arr[j],arr[imin]))
imin = j;
swap(arr[i],arr[imin]);
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
19

20. Сортировка выбором

void sortArray(int* arr, int size){
for(int i=0;i<size-1;i++){
int imin = i;
for(int j=i+1;j<size;j++)
if(arr[j]<arr[imin])
imin = j;
swap(arr[i],arr[imin]);
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
20

21. Сортировка выбором

void sortArray(int* arr, int size){
for(int i=0;i<size-1;i++){
int imin = i;
for(int j=i+1;j<size;j++)
if(arr[j]<arr[imin])
imin = j;
swap(arr[i],arr[imin]);
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
21

22. Сортировка выбором

void sortArray(int* arr, int size){
for(int i=0;i<size-1;i++){
int imin = i;
for(int j=i+1;j<size;j++)
if(arr[j]<arr[imin])
imin = j;
swap(arr[i],arr[imin]);
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
22

23. Сортировка выбором

void sortArray(int* arr, int size){
for(int i=0;i<size-1;i++){
int imin = i;
for(int j=i+1;j<size;j++)
if(arr[j]<arr[imin])
imin = j;
swap(arr[i],arr[imin]);
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
23

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

void insertionSort(int list[], int listLength)
{
for(int i = 1; i < listLength; i++)
{
int j = i - 1;
while(j >= 0 && list[j] > list[j + 1])
{
swap(list[j], list[j + 1]);
cout<<"\ndid";
j--;
}
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
24

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

void insertionSort(int list[], int listLength)
{
for(int i = 1; i < listLength; i++)
{
int j = i - 1;
while(j >= 0 && list[j] > list[j + 1])
{
swap(list[j], list[j + 1]);
cout<<"\ndid";
j--;
}
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
25

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

void insertionSort(int list[], int listLength)
{
for(int i = 1; i < listLength; i++)
{
int j = i - 1;
while(j >= 0 && list[j] > list[j + 1])
{
swap(list[j], list[j + 1]);
cout<<"\ndid";
j--;
}
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
26

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

void insertionSort(int list[], int listLength)
{
for(int i = 1; i < listLength; i++)
{
int j = i - 1;
while(j >= 0 && list[j] > list[j + 1])
{
swap(list[j], list[j + 1]);
cout<<"\ndid";
j--;
}
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
27

28. Сортировка слиянием

void mergeSort(int* buf, int l, int r){
if(l >= r) return;
int m = (l + r) / 2;
mergeSort(buf, l, m);
mergeSort(buf, m+1, r);
merge(buf, l, r, m);
}
void merge(int* buf, int l, int r, int m){
if(l >= r || m < l || m > r) return;
if(r == l + 1 && buf[l] > buf[r]){
swap(buf[l], buf[r]);
return;
}
int* tmp=new int[r-l+1];
for(int i=l,j=0;i<=r;i++, j++)
tmp[j]=buf[i];
for(int i=l,j=0,k=m-l+1;i<=r;i++){
if(j > m - l) buf[i] = tmp[k++];
else if(k > r - l) buf[i] = tmp[j++];
else
buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
}
}
Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
28

29. Сортировка слиянием

Основы Программирования 2023.
Верхошенцева Светлана Леонидовна
29